RT

链接: http://acm.hdu.edu.cn/showproblem.php?pid=1712

代码如下,大概就是一种有滚动数组一种没有

感觉两种应该是一样的但是只有一种能过，求助大佬两个有什么区别....

感谢!

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N = 1100;
int a[N][N];
int dp[N][N]; 

void solve(){
	int ans = 0;
	memset(dp, 0, sizeof dp);

	// 这是我写的版本，无滚动数组优化wa
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= 0; j--){
			for(int k = 1; k <= j; k++){
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + a[i][k]);
			}
		}
	}

// 这是滚动数组版本，能过
//	for(int i=1;i<=n;i++)
//		for(int j=m;j>=0;j--)
//	  		for(int k=1;k<=j;k++)
//	   	  		dp[j] = max(dp[j],dp[j-k]+a[i][k]);

	cout<<dp[n][m]<<'\n';	
} 

int main(){
	while(cin>>n>>m){
		if(!n&&!m) break;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				scanf("%d", &a[i][j]);
			}
		}
		solve();
	}
}