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