dp的，f[i][j]非0表示在加入第j个数后，可以得到i的值
f[i][j]的具体值表示这个i值是由谁加上或减去d[i]得到的，也就是记录的路径，话说我的做法很暴力：
int f[20000][100];
void main(){
	int i,j,n,t,d[100],ans[100]={0},m=0;
	scanf("%d%d",&n,&t);
	scanf("%d%d",&d[0],&d[1]);
	f[10000+d[0]-d[1]][1]=10000+d[0];
	for(i=2;i<n;i++){
		scanf("%d",&d[i]);
		for(j=0;j<20000;j++)if(f[j][i-1])f[j-d[i]][i]=f[j+d[i]][i]=j;			
	}
	t+=10000;
	for(i=n-1;i;i--){
		if(f[t][i]==t+d[i])ans[i]=0;
		else ans[i]=1;
		t=f[t][i];
	}
	for(i=1;i<n;i++)if(ans[i])printf("%d\n",i-m++);
	for(i=1;i<n;i++)if(!ans[i])printf("1\n");
}

• Re:100题留念...顺便说下思路 (8) songxuehui 2009-10-25 10:51:27