POJ 1946 Cow Cycling （dp推荐）-白红宇

POJ 1946 Cow Cycling （dp推荐）

阅读量：7054 次

发布时间：2019-06-28

本文共 1697 字，大约阅读时间需要 5 分钟。

那道题目看着好多状态。。。leader， speed， energy， distance，还有结果minute。

可以看到：

1、某头牛变成leader以后的energy是总能量 - distance。

2、当leader > N || energy < 0这些情况都是非法的。

3、distance == D这种情况是终止状态。

设 f[ld][sp][e][dis] 表示当前leader是ld，以速度sp到达能量剩余为e，行走距离为dis的状态所用的最少时间。

然后记忆化搜索可破

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #define CL(arr, val) memset(arr, (val), sizeof(arr))#define REP(i, n) for((i) = 0; (i) < (n); ++(i))#define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))#define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) ((l) + (r)) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) ((x) > 0 ? (x) : -(x))typedef long long LL;const double eps = 1e-12;const int inf = ~0u>>2;using namespace std;int dp[21][11][110][110];int N, D, E;int solve(int l, int sp, int e, int dis) { if(l > N || e < 0) return inf; if(dis == D) return 0; if(dp[l][sp][e][dis] != -1) return dp[l][sp][e][dis]; //printf("%d %d %d %d\n", l, sp, e, dis); int i, res = inf, n = sqrt(double(e)); for(i = 1; i <= n; ++i) { res = min(res, solve(l, i, e - i*i, dis + i) + 1); } res = min(res, solve(l + 1, sp, E - dis, dis)); dp[l][sp][e][dis] = res; return res;}int main() { //freopen("data.in", "r", stdin); //freopen("data.out", "w", stdout); while(~scanf("%d%d%d", &N, &E, &D)) { CL(dp,0XFF); int ans = solve(1, 0, E, 0); if(ans == inf) puts("0"); else printf("%d\n", ans); } return 0;}

ps：看到状态多的情况要冷静，另外要敢写。写错了可以改，如果写都不敢写那就没有下一步了。。。

转载地址：http://hvool.baihongyu.com/

你可能感兴趣的文章