poj 2609動的計画

DP,注意单组入力,题目的进程无效性,适合DP,
当時は車の数を推定できなかったため、スクロール配列を用いた.
DP状態の表示についてお話しします.
考えやすいのがDP【i】【j】【k】(現在の車番号、キュー1長、キュー2長)
明らかにMLE、実は私达は前の2次元があるだけでいいので、最后の1次元は前の2次元から推测することができます:k=sum【i】-j;
問題は存在性の問題に変わり、dp【i】【j】=dp【i-1】【j】|dp【i-1】【j-len【i】(それぞれキュー1に、キュー2に置く)
注意詳細処理
詳細はコードを参照してください.

#include<stdio.h>
#include<string.h>
const int maxn=10007;
bool dp[2][maxn];//   i   ，       J   
int  pre[501][maxn];
int sum[501];
int q[501];
void output(int ,int );
int main()
{
	int max,i,j,a,ans,nn,c,T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&max);
		nn=1,ans=0,c=0;
		max*=100;
		memset(sum,0,sizeof(sum));
		while(scanf("%d",&a)&&a)
			q[nn++]=a;
		sum[1]=q[1];
		for(i=2;i<nn;i++)
			sum[i]+=sum[i-1]+q[i];
		memset(dp,false,sizeof(dp));
		memset(pre,-1,sizeof(pre));
		dp[0][0]=true;
		for(i=1;i<nn;i++)
		{
			memset(dp[i&1],false,sizeof(dp[i&1]));
			for(j=max;j>=0;j--)//        
			{
				if(sum[i-1]-j>max)//       
					break;
				if(sum[i]-j<=max)//          
				{
					if(j-q[i]>=0)
						dp[i&1][j]=dp[(i-1)&1][j]|dp[(i-1)&1][j-q[i]];
					else dp[i&1][j]=dp[(i-1)&1][j];
					if(dp[(i-1)&1][j]) 
						pre[i][j]=0;//         
					else if(j-q[i]>=0&&dp[(i-1)&1][j-q[i]]) 
						pre[i][j]=1;
				}
				else if(j-q[i]>=0)
				{
					dp[i&1][j]=dp[(i-1)&1][j-q[i]];
					pre[i][j]=1;
				}
				if(dp[i&1][j])
				{
					c=j;
					ans=i;
				}
			}
			if(ans!=i) //            ，break
				break;
		}
		printf("%d
",ans);
		if(ans) 
			output(ans,c);
	}
	return 0;
}
void output(int x,int y)
{
	if(x<=0) return ;
	if(pre[x][y]==1)
	{
		output(x-1,y-q[x]);
		printf("port
");
	}
	else if(pre[x][y]==0)
	{
		output(x-1,y);
		printf("starboard
");
	}
	else if(pre[x][y]==-1)
	{
		while(1) puts("S");
	}
}