写两个题解，以示刷DP的重要性

HDOJ5464

题意：给定n和p，和n个整数，求选择任意k个数的和为p的倍数，k可以为0

很简单的想法：dp[i][j]为选前i个数，模p余数为j的方法数，那么dp[n][0]即为答案

细节：j的范围，每个数的大小只需保留-p到p内的值就好了

状态转移根据定义很好想的

int main(){
	//input;
	int i,j,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&p);
		for(i=1;i<=n;i++){
			scanf("%d",&num[i]);
			num[i]%=p;
		}
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(i=1;i<=n;i++)
			for(j=0;j<p;j++)
				dp[i][j]+=(dp[i-1][j]+dp[i-1][(j-num[i]+p)%p])%mod;
				
		/*for(i=1;i<=n;i++){
			for(j=0;j<p;j++) printf("%d ",dp[i][j]);
			cout<<endl;
		}*/
		printf("%d\n",dp[n][0]);
	}
	return 0;
}

2015合肥网赛第9题：HDOJ5492

想了两个小时，公式也是对的：实力推：

思路如下：把方差的公式列出来，然后左右同乘（n+m-1）的平方，然后就把平均值化成了求和，，，，剩下的就是怎么DP了

先说自己错误的思路：

Sqr【i】【j】为从（1，1）到（i，j）的平方和

Sum【i】【j】为从（1，1）到（i，j）的数和

然后Dp【i】【j】就是之前维护的公式的值：：：关键是这样水样例过了！

int t,n,m,avg,Min,mul;
ll Num[maxn][maxn];
ll Sum[maxn][maxn];
ll Sqr[maxn][maxn];
ll Dp[maxn][maxn];

void DP(){
	int i,j; 
	memset(Dp,0,sizeof(Dp));
	memset(Sum,0,sizeof(Sum));
	memset(Sqr,0,sizeof(Sqr));
	
	Sum[1][1]=Num[1][1];
	Sqr[1][1]=Num[1][1]*Num[1][1];
	Dp[1][1]=mul*Sqr[1][1]-Sum[1][1]*Sum[1][1];
	
	for(i=2;i<=n;i++){
		Sum[i][1]=Sum[i-1][1]+Num[i][1];
		Sqr[i][1]=Sqr[i-1][1]+Num[i][1]*Num[i][1];
		Dp[i][1]=Sqr[i][1]*mul-Sum[i][1]*Sum[i][1];
	}
	
	for(i=2;i<=m;i++){
		Sum[1][i]=Sum[1][i-1]+Num[1][i];
		
		Sqr[1][i]=Sqr[1][i-1]+Num[1][i]*Num[1][i];
		Dp[1][i]=Sqr[1][i]*mul-Sum[1][i]*Sum[1][i];
	}
	
	for(i=2;i<=n;i++)
		for(j=2;j<=m;j++){
			
			ll Sum1,Sum2,Dp1,Dp2,Sqr1,Sqr2;
			Sum1=Sum[i][j-1]+Num[i][j];
			Sqr1=Sqr[i][j-1]+Num[i][j]*Num[i][j];
			Dp1=Sqr1*mul-Sum1*Sum1;
			
			Sum2=Sum[i-1][j]+Num[i][j];
			Sqr2=Sqr[i-1][j]+Num[i][j]*Num[i][j];
			Dp2=Sqr2*mul-Sum2*Sum2;
			
			if (Dp1<Dp2){
				Dp[i][j]=Dp1;
				Sum[i][j]=Sum1;
				Sqr[i][j]=Sqr1;
			}
			else{
				Dp[i][j]=Dp2;
				Sum[i][j]=Sum2;
				Sqr[i][j]=Sqr2;
			}
		}
}

int main(){
	//input;
	int i,j;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%I64d",&Num[i][j]);
		mul=n+m-1;
		DP();
		printf("Case #%d: %I64d\n",Case,Dp[n][m]);
	}
	return 0;
}

少一维不满足无后效性了，走过的格子的和是影响结果的

也许f[i-1][j]的时候和是a比和是b的结果要好
但是 f[i][j]的时候和 a+x[i][j]就比和是b+x[i][j]的结果要差了

重要的话说三遍：谢谢我毛毛雨巨巨，谢谢我毛毛雨巨巨，谢谢我毛毛雨巨巨！

所以，正确姿势应该是，

f[i][j][k]表示走到i，j这个点，且经过的点权值和为k的情况下，权值的平方和最小为f[i][j][k]

他应该由  f[i-1][j] [k - a[i][j]] 和 f[i][j-1][k-a[i][j]] 转移来

这样就很容易AC了！

公式一样，思路一样，DP实现不同，差距就是这么大，下午几个小时的方向没有白费，下面贴代码：

int a[40][40];
int sum[100],n,m;
int f[40][40][1900];

int main(){
	//input;
	int t;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
		memset(f,0x7f7f7f7f,sizeof(f));
		
		memset(sum,0,sizeof(sum));
		f[1][1][a[1][1]]=a[1][1]*a[1][1];
		sum[0]=0;
		for(int i=1;i<=m;i++)
			sum[i]=sum[i-1]+a[1][i];
		for(int i=2;i<=m;i++)
			f[1][i][sum[i]]=f[1][i-1][sum[i-1]]+a[1][i]*a[1][i];
		
		memset(sum,0,sizeof(sum));
		sum[0]=0;
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+a[i][1];
		for(int i=2;i<=n;i++)
			f[i][1][sum[i]]=f[i-1][1][sum[i-1]]+a[i][1]*a[i][1];
		
		for(int i=2;i<=n;i++)
		for(int j=2;j<=m;j++){
			for(int k=0;k<=1800;k++){
				if (f[i][j-1][k]<=1000000)
					f[i][j][k+a[i][j]]=min(f[i][j][k+a[i][j]],f[i][j-1][k]+a[i][j]*a[i][j]);
				if (f[i-1][j][k]<=1000000)
					f[i][j][k+a[i][j]]=min(f[i][j][k+a[i][j]],f[i-1][j][k]+a[i][j]*a[i][j]);
			}
		}
		
		int ans=0x7f7f7f7f;
		for(int i=0;i<=1800;i++)
			if (f[n][m][i]<=1000000)
				ans=min(ans,(n+m-1)*f[n][m][i]-i*i);
		
		printf("Case #%d: %d\n",Case,ans);
	}
	return 0;
}

——————————————————————————————————————————————————————————————————

重要的事情说三遍：

国庆需要好好练习！

国庆需要好好练习！

国庆需要好好练习！