2015广州市选第四题题解
【题目大意】
其实这题题目描述就已经很详细了,也没啥废话,直接看题目就可以了。不过在这里说一下,那个所谓的“字符串”只是为了表达方便而已,并没有一个真实的字符串(输入样例里已经说了只是消掉字符在原来字符串的第i位的代价而已)。(好吧都是废话)
【分析】
如果不考虑旋转的部分,很显然可以用O(n^2)的DP,但是加入了选转就有了一些不同。我们考虑选转的问题,这个旋转相当于把原本指在b字符串的当前待消除字符,假设第j位中的j向后任意移动k个单位长度,然后在两次旋转操作之间就是一个【看上去有点点像朴素的DP】(由于只是大概搞懂了标程所以一些小细节还有待理解),而旋转前后的两部分是不会互相干扰答案的(无后效性)。然后貌似有一个二分来枚举k,最后找到最优解输出。
具体可以看标程。
标程一部分变量的大概用途:
记录类型route:ans:存储最后的答案,length:旋转后执行了几步操作
ro:ro[k]表示旋转了k个单位长度的结果。
f:DP用的数组
g:记录DP中间的操作
ll,rr:中间DP的范围(DP B字符串的哪一部分)
ps:感觉大部分都理解了,但是具体怎么弄还是不太清楚,同学们可以自行讨论。
【标程】
#include<stdio .h> #include<iostream> #include<string .h> #include<time .h> #include<algorithm> using namespace std; const int MAXN=1024; struct route { int x[MAXN< <1],y[MAXN<<1]; int length; int ans; }; int am[MAXN],an[MAXN],b[MAXN][MAXN]; route ro[MAXN],l,r; int m,n; int ll[MAXN],rr[MAXN]; int f[MAXN][MAXN],g[MAXN][MAXN]; void cal_route(int k,const route &l,const route &r) { int i,j,x,y; for (i=0;i<=m;i++) { ll[i]=(n<<1)-1; rr[i]=0; } for (i=0;i<l.length;i++) { if (l.y[i]<ll[l.x[i]]) ll[l.x[i]]=l.y[i]; } for (i=0;i<r.length;i++) { if (r.y[i]>rr[r.x[i]]) rr[r.x[i]]=r.y[i]; } for (i=0;i< =m;i++) { if (ll[i]<k) ll[i]=k; if (rr[i]>k+n) rr[i]=k+n; ll[i]-=k; rr[i]-=k; } for (i=0;i< =m;i++) for (j=ll[i];j<=rr[i];j++) g[i][j]=-1; f[0][0]=0; g[0][0]=0; int temp; for (i=0;i<=m;i++) //这一块就是DP,相信大家都看得懂 { for (j=ll[i];j<=rr[i];j++) { if (j+1<=rr[i]) { temp=f[i][j]+an[(j+k)%n]; if (g[i][j+1]==-1||temp<f[i][j+1]) { f[i][j+1]=temp; g[i][j+1]=1; } } if (i+1<=m&&j>=ll[i+1]) { temp=f[i][j]+am[i]; if (g[i+1][j]==-1||temp<f [i+1][j]) { f[i+1][j]=temp; g[i+1][j]=2; } } if (i+1<=m&&j+1<=rr[i+1]&&j+1>=ll[i+1]) { temp=f[i][j]+b[i][(j+k)%n]; if (g[i+1][j+1]==-1||temp</f><f [i+1][j+1]) { f[i+1][j+1]=temp; g[i+1][j+1]=3; } } } } x=m; y=n; i=0; while (1) { ro[k].x[i]=x; ro[k].y[i]=y+k; i++; if (g[x][y]==0) break; else if (g[x][y]==1) y--; else if (g[x][y]==2) x--; else //g[x][y]==3 { x--; y--; } } ro[k].length=i; ro[k].ans=f[m][n]; return; } void cal(int left,int right,const route &l,const route &r) { if (left>right) return; int mid=((left+right)>>1); cal_route(mid,l,r); cal(left,mid-1,l,ro[mid]); cal(mid+1,right,ro[mid],r); return; } int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); int i,j,t=1; //scanf("%d", &t); //不明觉厉的注释 while (t>0) { t--; scanf("%d %d",&m,&n); for (i=0;i<m ;i++) scanf("%d",am+i); for (i=0;i<n;i++) scanf("%d",an+i); for (i=0;i<m;i++) for (j=0;j<n;j++) scanf("%d",&b[i][j]); l.length=r.length=m+1; for (i=0;i<=m;i++) { l.x[i]=r.x[i]=i; l.y[i]=0; r.y[i]=(n<<1)-1; } cal_route(0,l,r); //返回的ro[0]是无视旋转的结果 for (i=0;i<ro[0].length;i++) { r.x[i]=ro[0].x[i]; r.y[i]=ro[0].y[i]+n; } r.length=ro[0].length; //这一行之前都像是初始化 cal(1,n-1,ro[0],r); //主要,用二分遍历所有的k int k=0; //找到最优解 for (i=1;i<n;i++) if (ro[i].ans<ro[k].ans) k=i; printf("%d\n",ro[k].ans); } return 0; }
发表回复