[luoguP1941] 飞扬的小鸟（DP）

传送门

动归，用f[i][j]表示到达第I列高度为j时最少需要飞的次数，容易想到最裸的转移：

f[i][j]=min(min(f[i-1][j-up[i-1]*k]+k),f[i-1][j+down[i-1]])

但是会超时

考虑怎么优化k的循环，发现k可以从k-1转移过来，从图上来理解就是比如k=2时，相当于可以先从i-1列飞一次飞到i列的j-up[i-1]位置，然后再往上跳一次跳到i的j位置，也就是f[i][j]可以从f[i]

[j-up[i-1]]+1转移来，这里需要注意几个地方

1.由于f[i][j-up[i-1]]相当于是中转的位置，所以无论那个位置是不是管道都要做

2.要保证f[i][j-up[i-1]]可以充当中转，所以必须先做一次只飞不掉的，再做一次掉下来的，否则会出现f[i][j-up[i-1]]位置可能是从i-1列掉下来得到的，此时不能充当中转

3.要特殊处理高度为m的情况（看题目）

——代码

 #include <cstdio>

 #include <iostream>

 const int INF = , N = , M = ;

 int n, m, k, b, ans = INF, sum;

 int x[N], y[N], l[N], h[N], f[][M];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int min(int x, int y)

 {

     return x < y ? x : y;

 }

 int main()

 {

     int i, j, p;

     n = read();

     m = read();

     k = read();

     for(i = ; i < n; i++)

     {

         x[i] = read();

         y[i] = read();

     }

     for(i = ; i <= k; i++)

     {

         p = read();

         l[p] = read();

         h[p] = read();

     }

     for(i = ; i <= n; i++)

     {

         for(j = ; j <= m; j++) f[i & ][j] = INF;

         for(j = x[i - ] + ; j <= m; j++)

             f[i & ][j] = min(f[i & ][j], f[i &  ^ ][j - x[i - ]] + ),

             f[i & ][j] = min(f[i & ][j], f[i & ][j - x[i - ]] + );

         for(j = m - x[i - ]; j <= m; j++)

             f[i & ][m] = min(f[i & ][m], f[i &  ^ ][j] + ),

             f[i & ][m] = min(f[i & ][m], f[i & ][j] + );

         for(j = ; j <= m - y[i - ]; j++) f[i & ][j] = min(f[i & ][j], f[i &  ^ ][j + y[i - ]]);

         if(l[i]) for(j = ; j <= l[i]; j++) f[i & ][j] = INF;

         if(h[i]) for(j = h[i]; j <= m; j++) f[i & ][j] = INF;

         if(l[i] || h[i])

         {

             b = ;

             for(j = l[i] + ; j < h[i]; j++)

                 if(f[i & ][j] < INF)

                 {

                     b = ;

                     break;

                 }

             if(b) sum++;

             else break;

         }

     }

     if(i == n + )

     {

         for(j = ; j <= m; j++) ans = min(ans, f[n & ][j]);

         printf("1\n%d\n", ans);

     }

     else printf("0\n%d\n", sum);

     return ;

 }

巴特西

[luoguP1941] 飞扬的小鸟（DP）

最新文章

热门文章