题目地址:TYVJ P1203 - 机器分配
简单DP 设dp[i][j]为前i个公司分配j个机器能得到的最大利益
dp[i][j] = max{prof[i][k] + dp[i - 1][j - k] | 0<=k<= j}
#include <cstdio> #include <memory.h> #include <algorithm> using namespace std; const int MAX = 101; int dp[MAX][MAX]; int prof[MAX][MAX]; int main(int argc, char const *argv[]){ int N, M; scanf("%d%d", &N, &M); for(int i = 1; i <= N; ++i){ for(int j = 1; j <= M; ++j){ scanf("%d", &prof[i][j]); } } memset(dp, 0, sizeof(dp)); for(int i = 1; i <= N; ++i){ for(int j = 1; j <= M; ++j){ for(int k = 0; k <= j; ++k){ dp[i][j] = max(dp[i][j], prof[i][k] + dp[i - 1][j - k]); } } } printf("%d\n", dp[N][M]); return 0; }
TYVJ P1203 - 机器分配,布布扣,bubuko.com
原文:http://blog.csdn.net/zxjcarrot/article/details/22485123