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< &lt;1],y[MAXN<&lt;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<&lt;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<&lt;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;
}

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据