hiho一下第173周《A Game》题目分析

8
0

《A Game》题目分析

每次轮到小Hi或者小Ho时，他们都面临同样的二选一决策：是拿走最左边的数，还是拿走最右边的数？

当然可以暴搜。时间复杂度O(2^N)会超时。此外比较容易发现贪心策略——总是拿走更大的数——是错误的。样例就是范例。

其实本题是一道非常经典的动态规划题目。

由于每次只能从数组首/尾拿走一个数，所以小Hi和小Ho在任何时候面对的残局都只可能是一段连续的子数组A[i..j]。我们不妨用f[i][j]表示当面对A[i..j]，先手最多能获得的得分。

如果我们能计算出所有f[i][j]的值，那么显然f[1][n]就是最终答案。

其中i = j的情况f[i]j的值是很容易计算的：f[i][j]=A[i]。因为只剩下A[i]一个数，先手只能拿走A[i]。

对于i < j的情况，先手P需要决策是拿走A[i]还是拿走A[j]?

如果拿走A[i]，那么对手Q面对的是A[i+1 .. j]，Q最多能获得的得分是f[i+1][j]。而且Q一定会按照得到f[i+1][j]这个得分的方式进行决策。所以先手P最大得分是sum(A[i .. j]) - f[i+1][j]。(A[i][j]的分数和减去P的得分)

同理如果拿走A[j]，先手P最大得分会是sum(A[i .. j]) - f[i][j-1]。

由于此时先手P可以二选一，所以f[i][j] = max{ sum(A[i .. j]) - f[i+1][j], sum(A[i .. j]) - f[i][j-1] } = sum(A[i .. j]) - min(f[i+1][j], f[i][j-1])。

注意sum(A[i .. j])可以通过预处理出前缀和再O(1)计算得出。

  • f[i][j] = max{ sum(A[i .. j]) - f[i+1][j], sum(A[i .. j]) - f[i][j-1] }这个不是表示f[i][j]=max(这段最左边的数，这段最右边的数) 么？，这样算的话f[i][j]不一直是单个数，没有和的感觉么？ 我觉得f[i][j] = max{ num[i] + f[i+1][j], num[i+j-1] + f[i][j-1] } 这样才有和的感觉啊，但是这样貌似有问题，请问是怎么回事啊？

  • 因为这样的和求出来对手拿的是最少的，不符合题意

  • 添加评论
  • ✖reply

3 answer(s)

0

记忆化搜索

include

include

include

using namespace std;

define Fin(i,f,t) for(int i = f; i <= t; ++i)

define Fde(i,f,t) for(int i = f; i >= t; --i)

define SfI(x) scanf("%d",&x)

define MAXN 2000

int dp[MAXN][MAXN],v[MAXN],N; bool visit[MAXN][MAXN];

int Dp(int i,int j){ if(i > j) return 0; if(i == j) return v[i]; if(visit[i][j]) return dp[i][j]; visit[i][j] = true; int max1 = v[i] + min(Dp(i+2,j),Dp(i+1,j-1)); int max2 = v[j] + min(Dp(i+1,j-1),Dp(i,j-2)); return dp[i][j] = max(max1,max2); } int main() { while(~SfI(N)){ Fin(i,1,N) SfI(v[i]); memset(visit,false,sizeof visit); printf("%d\n",Dp(1,N)); } return 0; }

暂时没想到自底向上

0

记忆化搜索可还行

0

为什么这样就AC

for (int i = n; i >= 1; i--) {
    for (int j = i + 2; j <= n; j++) {
        dp[i][j] = dp[i + 1][j] > dp[i][j - 1] ? s[j] - s[i - 1] - dp[i][j - 1] : s[j] - s[i - 1] - dp[i + 1][j];
    }
}

这样就不对？

for (int i = 3; i <= n; i++) {
    for (int j = 1; j + i - 1 <= n; j++) {
        int l = j, r = j + i - 1;
        dp[l][r] = dp[l + 1][r] > dp[l][r - 1] ? s[r] - s[l - 1] - dp[l][r - 1] : s[r] - s[l - 1] - dp[l + 1][r];
    }
}

第一个直接枚举左右端点，第二个先枚举长度再枚举起始点。

  • 窝也是先枚举的长度 再枚举的起点 然后疯狂wa

  • 肯定要先枚举长度，因为算长度的为x的dp时，要用到长度为x-1的dp，所以x-1的dp都要先求出来

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲