Codeforces 1629 F1. Game on sum (easy version) - DP, game, thinking

This way

The question ：

You have a number on your hand , At first it was 0, You can choose each time [0,k] Any real number in . Then it is up to the opponent to add or subtract this number . in total n round , And the opponent must have at least m Round plus the number in your hand . You want the numbers to be as big as possible , The opponent wants the number to be as small as possible . If you both make the best choice , Ask the maximum number .

Answer key ：

game … I'm a real dish . that 2000 The left-right game can push me on the ground and rub , Still need more practice

At the beginning, I wanted to follow it , I can't even model an example QAQ.
So set dp[n][m] Take a total of... For the present n round , The opponent should at least add m round .
After taking a round , Since the previous decision does not affect the subsequent situation , So either dp[n-1][m], Or become dp[n-1][m-1].
Suppose that the current round is x. So there are two cases in all ：
1.dp[n-1][m-1]+x
2.dp[n-1][m]-x
Which opponent will take ？ Of course, the smallest one min(dp[n-1][m-1]+x,dp[n-1][m]-x).
How to make this value as large as possible ？ When x=(dp[n-1][m-1]+dp[n-1][m])/2 When .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=2e3+5;
ll dp[N][N];
ll qpow(ll a,ll b){
    ll ans=1;for(;b;a=a*a%mod,b>>=1)if(b&1)ans=ans*a%mod;return ans;}
int main()
{
    
    int inv=qpow(2,mod-2);
    for(int i=1;i<N;i++)dp[i][i]=i;
    for(int i=2;i<N;i++)
        for(int j=1;j<i;j++)
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])*inv%mod;
    int t;
    scanf("%d",&t);
    while(t--){
    
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        printf("%lld\n",dp[n][m]*k%mod);
    }
    return 0;
}