Codeforces 566F
题目大意：给定$N$个数，任意两个数之间若存在一个数为另一个数的因数，那么这两个数存在边，求图中最大团。
分析：求一个图最大团为NP-Hard问题，一般不采用硬方法算。设$f[i]$表示数值为$i$的数的最大团，那么那么得到以下转移：
$f[i]=max \{ f[j]+1 \} j|i$
//cf 566f
//by Cydiater
//2016.11.4
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <queue>
#include <map>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,a[MAXN],f[MAXN],ans=0;
namespace solution{
void init(){
N=read();memset(f,0,sizeof(f));
up(i,1,N)f[a[i]=read()]=1;
}
void slove(){
sort(a+1,a+N+1);
up(i,1,N){
up(j,2,oo){
if(a[i]*j>a[N])break;
cmax(f[a[i]*j],f[a[i]]+1);
}
}
up(i,1,N)cmax(ans,f[a[i]]);
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 559C
题目大意：一张$N \times M$的地图，其中存在$T$个障碍点，询问从$(1,1)$到$(N,M)$不经过障碍点的道路方案数，只能向下和右走。
分析：首先考虑，如果没有障碍点，那么从$(1,1)$到$(N,M)$的方案数应该为$C_{N-1+M-1}^{N-1}$。有了这一点，就可以根据乘法原理搞DP。
设$f[i]$表示第$i$个障碍点的方案数，显然存在以下转移：
$f[i]=C_{x_i-1+y_i-1}^{x_i-1} - \sum C_{x_i-x_j+y_i-y_j}^{x_i-x_j} \times f[j]$
//CF 559c
//by Cydiater
//2016.11.4
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <bitset>
#include <set>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const ll MAXN=2e5+5;
const ll mod=1e9+7;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,M,T,fac[MAXN],f[MAXN],ans=0;
struct pll{ll x,y;};
pll xy[MAXN];
namespace solution{
inline bool cmp(pll a,pll b){return a.x==b.x?a.y<b.y:a.x<b.x;}
void init(){
N=read();M=read();T=read();
up(i,1,T)xy[i].x=read(),xy[i].y=read();
sort(xy+1,xy+T+1,cmp);
fac[0]=1;
up(i,1,200000)fac[i]=(fac[i-1]*i)%mod;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a){
ll x,y;exgcd(a,mod,x,y);
while(x<0)x+=mod;
return x;
}
ll C(ll x,ll y){return fac[y]*inv(fac[x]*fac[y-x]%mod)%mod;}
void slove(){
up(i,1,T){
f[i]=C(xy[i].x-1,xy[i].x+xy[i].y-2);
up(j,1,i-1){
f[i]-=f[j]*C(xy[i].x-xy[j].x,xy[i].x+xy[i].y-xy[j].x-xy[j].y)%mod;
(f[i]+=mod)%=mod;
}
}
ans=C(N-1,N+M-2);
up(i,1,T){
ans-=f[i]*C(N-xy[i].x,N+M-xy[i].x-xy[i].y);
(ans+=mod)%=mod;
(ans+=mod)%=mod;
}
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 545C
题目大意：给定以一个一维序列，每个序列上的元素有确定的坐标和高度，问最多能使多少个元素倒下，一个元素倒下为把$[x_i-h_i,x_i]$或把$[x_i,x_i+h_i]$的线段占据。
分析：贪心..好玄学啊。一句话策略，能向左倒就向左倒，能向右到而又不覆盖就向右倒，否则不倒，我不知道为什么QAQ。
//CF 545c
//by Cydiater
//2016.11.4
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <iomanip>
#include <bitset>
#include <set>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,ans;
ll pos;
struct Tree{
ll x,h;
}t[MAXN];
namespace solution{
inline bool cmp(Tree a,Tree b){return a.x<b.x;}
void init(){
N=read();
up(i,1,N){
int x=read(),h=read();
t[i]=(Tree){x,h};
}
sort(t+1,t+N+1,cmp);
}
void slove(){
ans=1;
if(N>=2)ans++;
pos=t[1].x;
up(i,2,N-1){
if(t[i].x-t[i].h>pos){ans++;pos=t[i].x;}
else if(t[i].x+t[i].h<t[i+1].x){ans++;pos=t[i].x+t[i].h;}
else pos=t[i].x;
}
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 543A
题目大意：有$N$个码农，每个码农码一行代码会出现$a_i$个bug，问码$M$行代码出现的bug数$\leq B$的方案数。
分析：很浅显的DP，设$f[i][j][k]$表示前$i$个码农，码了$j$行代码，出现了$k$个bug的方案数。
转移也很好想：$f[i][j][k]=f[i-1][j][k]+f[i][j-1][k-a_i]$
但是有很多细节，比方说要用滚动数组优化内存，然后$a_i$可能为0要照顾上$k=0$的方案。
//543A
//by Cydiater
//2016.11.4
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=505;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,B,mod,a[MAXN],f[3][MAXN][MAXN],ans=0,t=0;
namespace solution{
void init(){
N=read();M=read();B=read();mod=read();
up(i,1,N)a[i]=read();
}
void slove(){
up(i,1,N){
t^=1;memset(f[t],0,sizeof(f[t]));
f[t][0][0]=1;
up(j,1,M)up(k,0,B){
f[t][j][k]=f[t^1][j][k];
if(k>=a[i])(f[t][j][k]+=f[t][j-1][k-a[i]])%=mod;
}
}
up(i,0,B)(ans+=f[t][M][i])%=mod;
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 627D
题目大意：给定一颗无根树，你可以钦定哪一个点是根，钦定对于一个节点遍历边的顺序。要求DFS序的前$M$个点的节点的最小值最大。
分析：最小的最大，妥妥的二分。二分答案，然后把每一个权值大于等于的点标记一下，然后搞树规。
设$f[i]$为第$i$个点开始dfs最多有几个点是被标记了。对于一个节点的所有子树，如果一个子树全都被标记了，肯定优先选。这样的话就剩下一些点其全部遍历是不能全部都大于等于二分的出的下界。
而显然我们要取出其中最大的。儿子节点很好处理，考虑父亲，如果父亲节点所连接的其余节点都被标记了，也要选上，但并不添加进$f[i]$的值，而只是添加进要更新答案的值。但是如果存在点是没被标记的。
那么就不必选，因为这种情况在祖先是可以被考虑到的。另外一个地方，对于每一个节点要更新的答案，肯定是由一堆全被标记的子树（包括父亲），和两个未被完全标记的子树组合而成的。
为什么是两个？因为最后更新的答案当前节点不一定要作为最后的根，可以只是经历个的一个节点，而根节点在其中一个未被完全标记的子树中，画画图就可以发现这种情况是完全可能存在的。
//CF 627D
//by Cydiater
//2016.10.5
#include <iostream>
#include <iomanip>
#include <queue>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
const int MAXN=4e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,Val[MAXN],LINK[MAXN],len=0,leftt,rightt,mid,ans=0,siz[MAXN],sizt[MAXN],tol,f[MAXN];
int tag[MAXN];
struct edge{
int y,next;
}e[MAXN];
namespace solution{
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
inline void Insert(int x,int y){insert(x,y);insert(y,x);}
void init(){
N=read();M=read();
up(i,1,N)Val[i]=read();
up(i,1,N-1){
int x=read(),y=read();
Insert(x,y);
}
}
void pre_dfs(int node,int fa){
siz[node]=1;
Auto(i,node)if(e[i].y!=fa){
pre_dfs(e[i].y,node);
siz[node]+=siz[e[i].y];
}
}
void TreeDP(int node,int fa){
sizt[node]=tag[node];int max1=0,max2=0;
Auto(i,node)if(e[i].y!=fa){
TreeDP(e[i].y,node);
sizt[node]+=sizt[e[i].y];
if(siz[e[i].y]==sizt[e[i].y])f[node]+=sizt[e[i].y];
else if(f[e[i].y]>max1){max2=max1;max1=f[e[i].y];}
else if(f[e[i].y]>max2)max2=f[e[i].y];
}
if(!tag[node]){
f[node]=0;
return;
}else f[node]++;
if(tol-sizt[node]==N-siz[node])f[node]+=tol-sizt[node];
f[node]+=max1;
cmax(ans,f[node]+max2);
if(tol-sizt[node]==N-siz[node])f[node]-=tol-sizt[node];
}
bool check(int lim){
memset(tag,0,sizeof(tag));
memset(sizt,0,sizeof(sizt));
memset(f,0,sizeof(f));
ans=tol=0;
up(i,1,N)if(Val[i]>=lim){tag[i]=1;tol++;}
TreeDP(1,0);
return ans>=M;
}
void slove(){
pre_dfs(1,0);
leftt=1;rightt=1000000;
while(leftt+1<rightt){
mid=(leftt+rightt)>>1;
if(check(mid)) leftt=mid;
else rightt=mid;
}
if(check(rightt))cout<<rightt<<endl;
else cout<<leftt<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 730C
题目大意：一张$N$个点$M$条边的DAG，通过每条边需要1s，存在一些点上有一些商店，商店里的商品有一定的单价和数目，有$Q$个询问，每次询问位于$pos$点里需要$ned$个商品且只有$mon$个钱，问最小时间。
分析：二分，先把每个商店按单价排序（一个点可能存在多个商店），然后对于每询问,大力BFS出最短时间，然后二分答案，然后单价递增验证即可。
//CF 627F
//by Cydiater
//2016.11.6
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,M,LINK[MAXN],len=0,T,Q,head,tail,q[MAXN<<1],pos,ned,mon,tim[MAXN],TIM,leftt,rightt,mid;
struct edge{
ll y,next,v;
}e[MAXN];
struct SHOP{
ll val,rem,id;
}node[MAXN];
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
inline void Insert(int x,int y,int v){insert(x,y,v);insert(y,x,v);}
inline bool cmp(SHOP x,SHOP y){return x.val<y.val;}
void init(){
N=read();M=read();
up(i,1,M){
int x=read(),y=read();
Insert(x,y,1);
}
T=read();
up(i,1,T){
int pos=read(),rem=read(),val=read();
node[i].val=val;node[i].rem=rem;node[i].id=pos;
}
Q=read();sort(node+1,node+T+1,cmp);
}
void BFS(){
head=1;tail=0;q[++tail]=pos;
up(i,1,N)tim[i]=oo;tim[pos]=0;
for(;head<=tail;head++){
int node=q[head];cmax(TIM,tim[node]);
Auto(i,node)if(tim[e[i].y]==oo){
tim[e[i].y]=tim[node]+1;
q[++tail]=e[i].y;
}
}
}
ll get(ll lim){
ll tmp=ned,cost=0;
up(i,1,T)if(tim[node[i].id]<=lim&&tmp>0){
cost+=min(tmp,node[i].rem)*node[i].val;
tmp-=min(tmp,node[i].rem);
}
if(tmp>0)cost=oo;
return cost;
}
void slove(){
while(Q--){
pos=read();ned=read();mon=read();TIM=0;
BFS();leftt=0;rightt=TIM;
while(leftt+1<rightt){
mid=(leftt+rightt)>>1;
if(get(mid)<=mon) rightt=mid;
else leftt=mid;
}
if(get(leftt)<=mon) printf("%d\n",leftt);
else if(get(rightt)<=mon) printf("%d\n",rightt);
else puts("-1");
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 623B
题目大意：给定一个长度为$N$的序列，每个序列的值为$a_i$,你可以删除序列中的一段连续区间并消耗$A \times len$的代价，你也可以给任意几个元素增加或减少1，一次花费$B$的代价，要求最小的代价使得所有剩下的数的gcd大于1。
分析：首先，只允许删除一个线段而且不允许删除所有的元素，所有最后得到的所有数的gcd一定是$a_1,a_1+1,a_1-1,a_N,a_N+1,a_N-1$的中一个数的因数，所以把这六个数的所有素因子搞出来（至多36个），对于每个素数做一次DP，设$f[i][0/1/2]$分别表示未删除线段，正在删除线段，已删除线段，DP前进行一次预处理搞出$cost_i$表示第$i$个通过$\pm 1$来满足要求。
然后就可以得到以下转移：$f[i][0]=f[i-1][0]+cost[i]$
$f[i][1]=min(f[i-1][0],f[i-1][1])+A$
$f[i][2]=min(f[i-1][2],f[i-1][1])+cost[i]$
//CF 623B
//by Cydiater
//2016.11.7
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
#include <ctime>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const ll MAXN=1e6+5;
const ll oo=1LL<<53;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,A,B,a[MAXN],ans=oo,f[MAXN][3],cost[MAXN];//0 undel 1 deling 2 deled
map<ll,ll> check;
namespace solution{
void init(){
N=read();A=read();B=read();
up(i,1,N)a[i]=read();
}
void DP(ll fac){
memset(f,10,sizeof(f));
f[0][0]=0;
up(i,1,N){
cost[i]=oo;
if(a[i]%fac==0)cost[i]=0;
else if((a[i]+1)%fac==0||(a[i]-1)%fac==0)cost[i]=B;
}
up(i,1,N){
f[i][0]=f[i-1][0]+cost[i];
f[i][1]=min(f[i-1][0],f[i-1][1])+A;
f[i][2]=min(f[i-1][1],f[i-1][2])+cost[i];
cmin(f[i][0],oo);cmin(f[i][1],oo);cmin(f[i][2],oo);
}
cmin(ans,min(f[N][0],min(f[N][1],f[N][2])));
}
void Div(ll num){
ll lim=sqrt(1.0*num);
up(i,2,lim)if(num%i==0){
while(num%i==0)num/=i;
if(check[i])continue;
check[i]=1;DP(i);
}
if(num>1&&!check[num])DP(num);
}
void slove(){
Div(a[1]+1);Div(a[1]);Div(a[1]-1);
Div(a[N]+1);Div(a[N]);Div(a[N]-1);
}
void output(){
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
return 0;
}
Codeforces 445C
题目大意：给定一个$N$个点$M$条边的图,$M < N$,这些点构成了一些树，需要支持两种操作：1.询问一个点所在树的直径。2.可以以任意方式合并两个点所在的树，使得合并后的树的直径最小。
分析：写这道题前我甚至不知道怎么求树的直径QAQ，求一个树的直径，先随便选一个点，然后DFS出和这个点距离最远的点，然后再DFS出和这个点距离最远的点就是树的直径。可以用反证法证（反正会用就行）。
对于这道题，可以先把每个树的直径求出。然后每次合并时用并查集维护，对答案取一个最值就行，即$len_{xy}= max\{ len_x,len_y,(len_x+1) /2+(len_y+1)/2+1 \}$
//CF 455C
//by Cydiater
//2016.11.8
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
const int MAXN=6e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,fa[MAXN],Q,len=0,LINK[MAXN],tree[MAXN],cnt=0,dep[MAXN],dist,nd,opt;
bool vis[MAXN];
struct edge{
int y,next;
}e[MAXN];
namespace solution{
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
inline void Insert(int x,int y){insert(x,y);insert(y,x);}
int getf(int node){
if(node==fa[node]) return node;
fa[node]=getf(fa[node]);
return fa[node];
}
void init(){
N=read();M=read();Q=read();
up(i,1,N<<1)fa[i]=i;
up(i,1,M){
int x=read(),y=read();
Insert(x,y);
fa[getf(x)]=getf(y);
}
}
void dfs(int node,int father){
fa[node]=cnt;
Auto(i,node)if(e[i].y!=father){
dep[e[i].y]=dep[node]+1;
dfs(e[i].y,node);
}
if(dep[node]>dist){
dist=dep[node];
nd=node;
}
}
void slove(){
memset(dep,-1,sizeof(dep));
cnt=N;
up(i,1,N)if(dep[i]==-1){
cnt++;dist=nd=0;dep[i]=0;dfs(i,0);fa[i]=cnt;
dist=0;if(nd!=0){
dep[nd]=0;
dfs(nd,0);
}
tree[cnt]=dist;
}
while(Q--){
opt=read();int x,y;
if(opt==1){
x=read();
printf("%d\n",tree[getf(x)]);
}else{
x=read();y=read();x=getf(x);y=getf(y);
if(x==y)continue;
int tmp=max(tree[x],tree[y]);
cmax(tmp,(tree[x]+1)/2+(tree[y]+1)/2+1);
fa[y]=x;tree[x]=tmp;
}
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 274B
题目大意：一个有$N$个点的树，树的每一个节点上有一个权值，每次可以选取从含根的一个联通分量，然后把整体每个点的权值$\pm 1$。问至少需要多少次操作使得每一个点的权值都为0。
分析：典型的树规，设$f[i][0/1]$表示当前节点需要增加或减少多少次。然后可以得到$f[i][1/0]= max \{ f[son][1/0] \} $，对于每个节点DP完后，得到最后处理完的权值，然后把当前权值累计进$f[i][0/1]$中，最后$f[1][1]+f[1][0]$就是答案。
//CF 274B
//by Cydiater
//2016.11.8
#include <iostream>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <set>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
const ll MAXN=1e5+5;
const ll oo=1LL<<50;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,LINK[MAXN],len=0;
ll Val[MAXN],f[MAXN][2];
struct edge{
int y,next;
}e[MAXN<<1];
namespace solution{
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
inline void Insert(int x,int y){insert(x,y);insert(y,x);}
void init(){
N=read();
up(i,2,N){
int x=read(),y=read();
Insert(x,y);
}
up(i,1,N)Val[i]=read();
memset(f,0,sizeof(f));
}
void TreeDP(int node,int father){
Auto(i,node)if(e[i].y!=father){
TreeDP(e[i].y,node);
cmax(f[node][1],f[e[i].y][1]);
cmax(f[node][0],f[e[i].y][0]);
}
Val[node]+=f[node][1];Val[node]-=f[node][0];
f[node][1]+=Val[node]<0?-Val[node]:0;
f[node][0]+=Val[node]>0?Val[node]:0;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
TreeDP(1,0);
cout<<f[1][0]+f[1][1]<<endl;
return 0;
}
Codeforces 676C
题目大意：给定一个长为$N$的$ab$串，你可以更改$K$个字符，问修改后最长的连续相同的字符有多长。
分析：看起来是个zzDP？其实并不是，二分出长度，然后枚举验证即可。
//CF 676C
//by Cydiater
//2016.11.8
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <queue>
#include <map>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,K,A[MAXN],B[MAXN],leftt,rightt,mid;
char s[MAXN];
namespace solution{
void init(){
N=read();K=read();
scanf("%s",s+1);
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
up(i,1,N){
A[i]=A[i-1];B[i]=B[i-1];
if(s[i]=='a')A[i]++;
else B[i]++;
}
}
int check(int len){
int ans=oo;
up(i,1,N-len+1)
cmin(ans,min(A[i+len-1]-A[i-1],B[i+len-1]-B[i-1]));
return ans;
}
void slove(){
leftt=0;rightt=N;
while(leftt+1<rightt){
mid=(leftt+rightt)>>1;
if(check(mid)<=K) leftt=mid;
else rightt=mid;
}
if(check(rightt)<=K) cout<<rightt<<endl;
else cout<<leftt<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 727F
题目大意：给定你一个数列，数列第$i$的值为$a_i$，其前$N$项和为$S_N$，有$M$个$b$,对于每个$b$要求你输出一个数，使得在数列中删除这些数后任意$S_N$均为非负数。
分析：很简单的题目，如果数据范围小的话，大力DP即可，这里面数据范围太大，转换思想采用DP预处理。设$f[i][j]$表示对于$[i,N]$，删除$j$个数使得其后$N-i+1$项的最小值最大的值。很容易得到转移方程：
$f[i][j]= max \{ f[i+1][j-1],min(f[i+1][j],a[i]) \}$
对于每个询问二分即可。
//CF 727F
//by Cydiater
//2016.11.9
#include <iostream>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=1e3+5;
const int oo=0x3f3f3f3f;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,M,a[MAXN],f[MAXN][MAXN],leftt,rightt,mid;
namespace solution{
void init(){
N=read();M=read();
up(i,1,N)a[i]=read();
}
void slove(){//pre DP
memset(f,-10,sizeof(f));
f[N+1][0]=0;
down(i,N,1){
f[i][0]=min(f[i+1][0]+a[i],a[i]);
up(j,1,N-i+1)cmax(f[i][j],max(f[i+1][j-1],min(f[i+1][j]+a[i],a[i])));
}
while(M--){
ll lim=read();
leftt=0;rightt=N;
while(leftt+1<rightt){
mid=(leftt+rightt)>>1;
if(f[1][mid]+lim>=0) rightt=mid;
else leftt=mid;
}
if(f[1][leftt]+lim>=0)printf("%d\n",leftt);
else printf("%d\n",rightt);
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 219D
题目大意：有一颗由有向边组成的“树”，要求询问最少的修改次数使得存在一个点可以到达任意一点，一次修改为给一个正向边添加一条反向边。
分析：愚蠢的树规。设$f[i]$表示如果$i$节点为所求节点，那么需要修改几条边，做两次树规，第一次得到对于其子树的$f[i]=\sum f[son]+edge_{(i,son)}$
第二次得到对于其子树外的:$f[i]=f[father]-edge_{(father,son)}+edge_{(father,son)} xor 1$
//CF 219D
//by Cydiater
//2016.11.9
#include <iostream>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
const int MAXN=4e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,LINK[MAXN],len=0,f[MAXN],ans=oo;
struct edge{
int y,next,v;
}e[MAXN];
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
void init(){
N=read();
up(i,1,N-1){
int x=read(),y=read();
insert(x,y,0);
insert(y,x,1);
}
}
void TreeDP1(int node,int father){
Auto(i,node)if(e[i].y!=father){
TreeDP1(e[i].y,node);
f[node]+=f[e[i].y]+e[i].v;
}
}
void TreeDP2(int node,int father){
cmin(ans,f[node]);
Auto(i,node)if(e[i].y!=father){
f[e[i].y]=f[node]-e[i].v+(e[i].v+1)%2;
TreeDP2(e[i].y,node);
}
}
void slove(){
memset(f,0,sizeof(f));
TreeDP1(1,0);
TreeDP2(1,0);
cout<<ans<<endl;
up(i,1,N)if(f[i]==ans)printf("%d ",i);
puts("");
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}
Codeforces 626F
题目大意：一个班级里有$N$个人，每个人都能完成一些工作，第$i$个人完成一项工作的时间为$a_i$，这$N$个人可以分成若干个组，一个组的不平衡度为$a_{max}-a_{min}$,要求有多少种分组情况可以使总不平衡度$\leq K$。
分析：神奇的DP，直接的思路行不通。设$f[i][j][k]$表示升序排完后的前$i$个人，有$j$个组还没有最大值，但有最小值，且总不平衡度$\leq k$的方案数。
然后可以得到以下转移:
首先对于第$i$个数，和第$i-1$个数做差，即$delta=a_i-a_{i-1}$,因为还有$j$个组仍在分配，所以把这个差值分配给各组，得$v=delta \times j +k$。便存在以下转移方程：
$f[i][j+1][v]+=f[i-1][j][k]$新的元素单独分一个未结束的组
$f[i][j][v]+=f[i-1][j][k]$新的元素分一个已结束的组
$f[i][j][v]+=f[i-1][j][k] \times j$新的元素分到一个未结束的组且不结束该组
$f[i][j-1][v]+=f[i-1][j][k] \times j$新的元素分到一个未结束的组且结束改组
//CF 626F
//by Cydiater
//2016.11.10
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <set>
using namespace std;
#define ll long long
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const ll MAXN=205;
const ll MAXK=1005;
const ll mod=1e9+7;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,K,f[2][MAXN][MAXK],a[MAXN],t=0,ans=0;
namespace solution{
void init(){
N=read();K=read();
up(i,1,N)a[i]=read();
sort(a+1,a+N+1);
}
void slove(){
memset(f,0,sizeof(f));
f[t][0][0]=f[t][1][0]=1;
up(i,2,N){
t^=1;
memset(f[t],0,sizeof(f[t]));
up(j,0,i){
ll delta=a[i]-a[i-1];delta*=j;
up(k,0,K){
ll v=delta+k;if(v>K)continue;
(f[t][j+1][v]+=f[t^1][j][k])%=mod;
(f[t][j][v]+=f[t^1][j][k])%=mod;
if(j>0)(f[t][j][v]+=f[t^1][j][k]*j)%=mod;
if(j>0)(f[t][j-1][v]+=f[t^1][j][k]*j)%=mod;
}
}
}
up(i,0,K)(ans+=f[t][0][i])%=mod;
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
return 0;
}