Hdu 1712 ACboy needs your help(DP_リュックサック)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1712
A[i][j]は、n科目を与え、m日でこのn科目を復習し、n*mのマトリクスAを与え、j日でi科目を復習して収益を得ることを示す.m日復習で異なる授業で得た最大収益を聞く.
问题解决の考え方:本题自体は难しくありませんが、データが与えるのはとても迷って、最初は1科目を2回复习することができると思って、それからn*mの収益をn*mの品物として01リュックサックの処理を行って、华丽に1つのWaに戻ることを提出します.もう一度テーマを見て、恥ずかしいので、違う授業を選ぶように要求しました.それはリュックサックをグループ化して、この授業は一度しか復習できないことを保証します.
     状態遷移方程式:dp[k]=min(dp[k],dp[k-j]+pro[i][j])(iはiゲート目の課程を表し,kは日数を表し,pro[iゲート目はj日の収益を表す).複雑度(O(n*m*m).ここでは日数の列挙順序が大きいから小さいまでに注意し,計算ごとに必要な状態が前回であることを保証してこそ,後効性を保証することができる.
テストデータ:

 2 34 4 13 2 11 24 4 
  
コード:
#include <stdio.h>
#include <string.h>
#define MAX 110


int n,m,ans,dp[MAX];
int pro[MAX][MAX];


int main()
{
	int i,j,k,t;


	while (scanf("%d%d",&n,&m),n+m) {

		for (i = 1; i <= n; ++i) 
			for (j = 1; j <= m; ++j)
				scanf("%d",&pro[i][j]);


		memset(dp,0,sizeof(dp));
		for (i = 1; i <= n; ++i)
			for (k = m; k >= 1; --k)
				for (j = k; j >= 1; --j)
					if (dp[k-j] + pro[i][j] > dp[k])
						dp[k] = dp[k-j] + pro[i][j];
		
					
		for (ans = i = 0; i <= m; ++i)		
			if (dp[i] > ans) ans = dp[i];
		printf("%d
",ans);
	}
}
  
ZeroClockオリジナルですが、 たちは  なので  できます.