首先明确一点:最优解必为奶牛1..n-1轮流领跑,奶牛n撞线。且跑了x圈后,未领跑过的奶牛都耗费了x的体力。
设f[i][j][k]表示前i-1头奶牛已领跑,现在由第i头奶牛领跑,一共跑了j圈,奶牛i耗费了k的体力。
则f[i][j][k]可以转移到f[i][j + p][k + p2](耗费1分钟,奶牛i以p圈/分钟的速度继续领跑),也可转移到f[i + 1][j][j](换成奶牛i + 1领跑,不耗费时间)。
时间复杂度为O(nde2.5)。


/*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-1 10:45:17
File Name: pku1946.cpp
Description: 
***********************************************************************
*/

#include 
<iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef 
long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template 
<class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template 
<class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

int n, d, e;
int f[22][101][101];

int main()
{
    scanf(
"%d%d%d"&n, &e, &d);
    
for (int i = 0; i <= n; i++)
        
for (int j = 0; j <= d; j++)
            
for (int k = 0; k <= e; k++)
                f[i][j][k] 
= maxint;
    f[
1][0][0= 0;
    
for (int i = 1; i <= n; i++)
        
for (int j = 0; j <= d; j++)
            
for (int k = 0; k <= e; k++if (f[i][j][k] < maxint)
            
{
                
for (int p = 1; k + p * p <= e; p++)
                    f[i][j 
+ p][k + p * p] <?= f[i][j][k] + 1;
                f[i 
+ 1][j][j] <?= f[i][j][k];
            }

    
int ans = maxint;
    
for (int j = 0; j <= e; j++)
        ans 
<?= f[n][d][j];
    
if (ans == maxint) printf("0\n");
    
else printf("%d\n", ans);
    
return 0;
}
posted on 2007-09-01 11:42 Felicia 阅读(469) 评论(1)  编辑 收藏 引用 所属分类: 动态规划
Comments
  • # re: [动态规划]pku1946
    程文华
    Posted @ 2009-04-25 21:13
    可以从你这学到很多!!!谢谢你.真的很感谢  回复  更多评论   

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