| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:dp方法很好,这题挺适合dp的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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator