首页 > 其他 > 详细

TYVJ P1203 - 机器分配

时间:2014-03-29 15:35:16      阅读:360      评论:0      收藏:0      [点我收藏+]

题目地址: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

TYVJ P1203 - 机器分配

原文:http://blog.csdn.net/zxjcarrot/article/details/22485123

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!