A. 【NOIP 2010 提高组】机器翻译
一个队列解决。
#include<bits/stdc++.h> using namespace std; int m,n,tot,i=0; bool a[10010]; queue<int> q; int main(){ // freopen("translate.in","r",stdin); // freopen("translate.out","w",stdout); cin>>m>>n; for(int k=1;k<=n;k++){ int x; scanf("%d",&x); if(!a[x]){ if(i==m){ i--; a[q.front()]=0; q.pop(); } q.push(x); a[x]=1; tot++; i++; } } cout<<tot; return 0; }这题暴力搜索过不了，所以要dp，还要四维的。
#include<bits/stdc++.h> using namespace std; int n,m,s[351],b,card[5],dp[41][41][41][41]; int main(){ // freopen("tortoise.in","r",stdin); // freopen("tortoise.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>s[i]; } for(int i=1;i<=m;i++){ cin>>b; card[b]++; } dp[0][0][0][0]=s[1]; for(int w=0;w<=card[1];w++){ for(int x=0;x<=card[2];x++){ for(int y=0;y<=card[3];y++){ for(int z=0;z<=card[4];z++){ int t=w+x*2+y*3+z*4+1; if(w)dp[w][x][y][z]=max(dp[w][x][y][z],dp[w-1][x][y][z]+s[t]); if(x)dp[w][x][y][z]=max(dp[w][x][y][z],dp[w][x-1][y][z]+s[t]); if(y)dp[w][x][y][z]=max(dp[w][x][y][z],dp[w][x][y-1][z]+s[t]); if(z)dp[w][x][y][z]=max(dp[w][x][y][z],dp[w][x][y][z-1]+s[t]); } } } } cout<<dp[card[1]][card[2]][card[3]][card[4]]; return 0; }先排序，再用并查集，把没有仇恨的两个罪犯放到一起，如果两个有仇恨的罪犯被放到了一起，直接输出。
#include<bits/stdc++.h> using namespace std; struct node{ int x,y,w; }f[100001]; int n,m,a[20001],b[20001]; bool comp(node a,node b){ return a.w>b.w; } int find(int x){ if(a[x]!=x){ a[x]=find(a[x]); } return a[x]; } void join(int x,int y){ int i=find(a[x]),j=find(a[y]); if(i!=j){ a[i]=j; } } bool check(int x,int y){ int i=find(x),j=find(y); if(i==j)return 1; return 0; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].w); } for(int i=1;i<=n;i++){ a[i]=i; } sort(f+1,f+1+m,comp); for(int i=1;i<=m;i++){ if(check(f[i].x,f[i].y)){ printf("%d",f[i].w); return 0; } else{ if(!b[f[i].x]){ b[f[i].x]=f[i].y; } else{ join(b[f[i].x],f[i].y);//敌人的敌人是朋友 } if(!b[f[i].y]){ b[f[i].y]=f[i].x; } else{ join(b[f[i].y],f[i].x); } } } cout<<0; return 0; }先用bfs把每个水源能到达的地方找出来，然后再dp找最少建多少个。最开始的时候想要用dfs解第二问，结果10分。。
#include<bits/stdc++.h> using namespace std; struct node{ int x,y,h; }now; struct fuck{ int l,r; }s[501]; int n,m,mapp[501][501],ne[4][2]={{1,0},{-1,0},{0,1},{0,-1}},tot; int f[501][501],dp[501]; bool b[501],book[501][501]; void bfs(int x){ memset(book,false,sizeof(book)); now.x=1; now.y=x; now.h=mapp[1][x]; queue<node> q; q.push(now); while(!q.empty()){ int tx,ty,th; book[q.front().x][q.front().y]=1; if(q.front().x==n){ b[q.front().y]=1; s[x].l=min(s[x].l,q.front().y); s[x].r=max(s[x].r,q.front().y); } for(int i=0;i<4;i++){ tx=q.front().x+ne[i][0]; ty=q.front().y+ne[i][1]; th=mapp[tx][ty]; if(tx>n||tx<1||ty>m||ty<1||th>=q.front().h||book[tx][ty]){ continue; } book[tx][ty]=1; now.x=tx; now.y=ty; now.h=th; q.push(now); } q.pop(); } } int main(){ // freopen("flow.in","r",stdin); // freopen("flow.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&mapp[i][j]); } } for(int i=1;i<=m;i++){ s[i].l=999999; } for(int i=1;i<=m;i++){ bfs(i); } for(int i=1;i<=m;i++){ if(!b[i]){ tot++; } } if(tot){ cout<<0<<endl<<tot; return 0; } memset(b,false,sizeof(b)); cout<<1<<endl; //用fz[i][j]来表示i和j之间最少需要建多少座蓄水厂，用d[i]来表示1~n最少需要多少座蓄水厂 for(int i=1;i<=m;i++){ dp[i]=999999; for(int j=1;j<=m;j++){ f[i][j]=999999; } } for(int t=1;t<=m;t++){ if(s[t].r){ for(int i=s[t].l;i<=s[t].r;i++){ for(int j=i;j<=s[t].r;j++){ f[i][j]=1; if(i==1){ dp[j]=1; } } } } } for(int i=1;i<=m;i++){ for(int j=1;j<=i-1;j++){ dp[i]=min(dp[i],dp[j]+f[j+1][i]); } } cout<<dp[m]; return 0; }