Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:dp方法很好,这题挺适合dp的

Posted by zyz913614263 at 2011-12-19 16:28:07 on Problem 1042
In Reply To:dp方法过了!!!!!!! Posted by:threedonkey at 2011-07-08 21:30:20
> #include <stdio.h>
> #include <string.h>
> 
> #define MAXN 30
> #define MAXM 300
> #define INF 0x3333333
> 
> int dp[MAXN][MAXM], path[MAXN][MAXM], f[MAXN], t[MAXN], d[MAXN], times[MAXN], m;
> 
> int sum(int i, int time){
> 	int ans  = (f[i] + f[i] - d[i] * (time - 1)) * time / 2;
> 	return ans;
> }
> 
> void Gettimes(int p, int time){
> 	if(p <= 1) return;
> 	m -= (times[p] = time) + t[p];
> 	Gettimes(p - 1, path[p - 1][m]);
> }
> 
> int main(){
> 	int n, i, j, k, temp, CASE = 0;
> 	//freopen("output.out", "w", stdout);
> 	while(~scanf("%d", &n), n){
> 		scanf("%d", &m);
> 		m = m * 12;
> 		for(i = 0; i <= n; i ++)
> 			for(j = 0; j <= m; j ++)
> 				if(!i) dp[i][j] = 0;
> 				else dp[i][j] = -1;
> 		memset(path, -1, sizeof(path));
> 		t[1] = 0;
> 		for(i = 1; i <= n; i ++) scanf("%d", &f[i]);
> 		for(i = 1; i <= n; i ++) scanf("%d", &d[i]);
> 		for(i = 2; i <= n; i ++) scanf("%d", &t[i]);
> 		int max = - INF, p;
> 		for(i = 1; i <= n; i ++){
> 			for(j = t[i]; j <= m; j ++){
> 				for(k = 0; k <= j - t[i]; k ++)
> 					if(dp[i - 1][k] > -1 && dp[i - 1][k] + sum(i, j - k - t[i]) >= dp[i][j]){
> 						dp[i][j] = dp[i - 1][k] + sum(i, j - k - t[i]);
> 						path[i][j] = j - k - t[i];
> 					}
> 				if(j > 0 && path[i][j - 1] != -1){
> 					temp = (f[i] - path[i][j - 1] * d[i]) < 0 ? 0 : (f[i] - path[i][j - 1] * d[i]);
> 					if(dp[i][j] < dp[i][j - 1] + temp){
> 						dp[i][j] = dp[i][j - 1] + temp;
> 						path[i][j] = path[i][j - 1] + 1;
> 					}
> 				}
> 			}
> 			if(max < dp[i][m]){max = dp[i][m]; p = i;}
> 		}
> 		memset(times, 0, sizeof(times));
> 		Gettimes(p, path[p][m]);
> 		times[1] = m;
> 		if(CASE) printf("\n");
> 		for(i = 1; i < n; i ++) printf("%d, ", times[i] * 5);
> 		printf("%d\n", times[n] * 5);
> 		printf("Number of fish expected: %d\n", max);
> 		CASE = 1;
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator