P2795 题解

baiABC · 2022-07-02 23:19:48 · 题解

这题网上都是清一色的 dfs，但是其实直接 dp 也可以。

设 f(j,i,v,x) 表示 (i,j) 位置当前速度为 v，潜水时间为 x 的最大答案（本格得到的钱不计），则容易递推更新后继状态，f(m,1,0,0) 即为答案。

先解决空间问题。首先 j 一维可以用滚动数组，然后由于 k\leq 10，所以 -21\times 10\leq v\leq21\times 10，可以开下。v 可能是负数，给 v 加上 300 变成正数。

再考虑时间，可以限制下一个阶段枚举的 v 的范围。时间复杂度 O(mnk^2\cdot\max w)，可以过。

DP 注意细节。

#include <bits/stdc++.h>
using namespace std;
int dp[2][105][605][15], a[105][1005][2];
void upd(int &x, int y)
{
   x = max(x, y);
}
int main()
{
   ios::sync_with_stdio(0);
   int n, m, k; cin >> n >> m >> k;
   for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= m; ++j)
      {
         char c; cin >> c;
         a[i][j][0] = c=='v';
         cin >> a[i][j][1];
      }
   memset(***dp, 0x80, sizeof dp); // -INF
   dp[1][1][300][0] = 0; // 下面 v 都加了 300
   int lalv = 0, larv = 0, lv = 300, rv = -300;
   for(int i = 1; i < m; ++i)
   {
      int r = i & 1, tr = r^1;
      for(int j = 1; j <= n; ++j)
      {
         if(j == 1)
         {
            int ts = dp[r][1][300][0];
            if(ts == 0x80808080) continue;
            if(!a[1][i][0]) ts += a[1][i][1];
            lv = rv = 0;
            upd(dp[tr][1][300][0], ts);
            if(n > 1) upd(dp[tr][2][301][1], ts), rv = 1;
            continue;
         }
         for(int v = lalv; v <= larv; ++v)
         {
            int tv = v;
            if(a[j][i][0]) tv += a[j][i][1];
            for(int x = 1; x < k; ++x)
            {
               int ts = dp[r][j][v+300][x];
               if(ts == 0x80808080) continue;
               if(!a[j][i][0]) ts += a[j][i][1];
               int tj = j+tv;
               tj = min(tj, n);
               if(tj <= 2)
               {
                  lv = min(lv, 0);
                  rv = max(rv, 0);
                  upd(dp[tr][1][300][0], ts);
                  if(tj < 1) continue;
               }
               if(x == k-1) continue;
               if(tj > 1)
               {
                  lv = min(lv, tv); rv = max(rv, tv);
                  upd(dp[tr][tj][tv+300][x+1], ts);
               }
               if(tj > 2)
               {
                  lv = min(lv, tv-1); rv = max(rv, tv-1);
                  upd(dp[tr][min(n,j+tv-1)][tv-1+300][x+1], ts);
               }
               if(n > 1)
               {
                  lv = min(lv, tv+1); rv = max(rv, tv+1);
                  upd(dp[tr][min(n,tj+1)][tv+1+300][x+1], ts);
               }
            }
         }
      }
      lalv = lv; larv = rv;
      lv = 300; rv = -300;
      memset(dp[r][0][0], 0x80, sizeof dp[r]);
      // 滚动数组要清空！
   }
   cout << dp[m&1][1][300][0]+(a[1][m][0]?0:a[1][m][1]) << '\n';
   return 0;
}