gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
dp[i][j]:第i分钟疲劳度为j时的最大路径值
转移方程:
dp[i][j] = dp[i - 1][j - 1] + distance[i] ( j  > 0 )
dp[i][0] = max (dp[i - 1][0], dp[i - j][j](i - j >= j && j <= M))
 1#include <cstdio>
 2
 3const int SIZE_T = 10001;
 4const int SIZE_M = 501;
 5
 6int dp[SIZE_T][SIZE_M];
 7
 8int T, M, dist[SIZE_T];
 9
10void Solve()
11{
12    int i, j;
13
14    for ( i = 0; i <= M; ++i )
15        dp[0][i] = 0;
16
17    for ( i = 1; i <= T; ++i )
18    {
19        dp[i][0] = dp[i - 1][0];
20        for ( j = 1; i - j >= j && j <= M; ++j )
21        {
22            dp[i][0] = (dp[i][0] > dp[i - j][j] ? dp[i][0] : dp[i - j][j] );
23        }
24
25        for ( j = 1; j <= M; ++j )
26        {
27            dp[i][j] = dp[i - 1][j - 1] + dist[i]; 
28                
29        }
30    }
31    
32    printf("%d\n", dp[T][0]);
33}
34
35int main()
36{
37    int i;
38    scanf("%d %d", &T, &M);
39
40    for ( i = 1; i <= T; ++i )
41        scanf("%d", &dist[i]);
42
43    Solve();
44
45    return 0;
46}
posted on 2009-03-19 23:12 阅读(378) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理