题解：CF1628D1 Game on Sum (Easy Version)

· · 题解

Game on Sum(Easy Version)

逆天冲刺 NOIP2024 题单可做题之一。

首先看到题目是一个想让最后结果较大，一个想让最后结果较小，两者均选择最优策略，所以可以考虑 \text{dp}，经典套路了。

然后设 f_{i,j} 为用掉 i 轮且使用了 j 次加法后的对应的 x 的值，可以知道 f_{n,m} 为最后的结果。

然后对于 Bob（他想要让最后结果较小）的转移方程就很明显了。

f_{i,j}=\min(f_{i-1,j}-t,f_{i-1,j-1}+t)

这里 f_{i-1,j} 表示上一次不使用加法，f_{i-1,j-1}表示上一次使用加法（似乎很明显吧）。

而 Alice 希望这个结果最大，因此我们可知其会让 f_{i-1,j}-t=f_{i-1,j-1}+t（很明显是因为这里要取 \min）。

那么用最基本的等式的基本性质可以解一下上面那个式子去求出 t 的值。

f_{i-1,j}-t-(f_{i-1,j-1}+t)=0 2\times t=f_{i-1,j}-f_{i-1,j-1} t=\frac{f_{i-1,j}-f_{i-1,j-1}}{2}

我们解出 t 的之后可以带回原本的转移方程来求出对应的 f_{i,j} 了。

f_{i,j}=f_{i-1,j-1}+\frac{f_{i-1,j}-f_{i-1,j-1}}{2} f_{i,j}=\frac{f_{i-1,j}+f_{i-1,j-1}}{2}

边界值 f_{i,0}=0,f_{i,i}=i\times k，然后直接大力 \text{dp} 即可。

这是朴素代码，复杂度是 \text O(Tnm) 无法通过此题。

namespace solve{
    inline int read(){
        int s=0,w=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
        return s*w;
    }
    inline void write(const int x){
        if(x>=10) write(x/10);
        putchar(x%10+'0');
    }
    inline void print(const int x,string s){
        if(x<0) putchar('-');
        write(x<0?-x:x);
        int len=s.size();
        for_(i,0,len-1) putchar(s[i]);        
    }
    int f[2000][2000];
    inline void In(){
        const int mod=1e9+7,inv=5e8+4;
        int T=read();
        while(T--){
            int n=read(),m=read(),k=read();
            for_(i,1,n){
                f[i][i]=i*k%mod;
            }
            for_(i,2,n){
                for_(j,1,i-1){
                    f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod*inv%mod;
                }
            }
            print(f[n][m],"\n");
        }
    }
}

那咋办呢？完全可以 \text O(nm) 预处理一遍，然后 \text O(1) 去查询。

但是这样就有个问题，原本我们是让 f_{i,i}=i\times k，而现在我们需要让 f_{i,i}=i，在查询 f_{n,m} 的时候乘上 k。

复杂度 \text{O}(nm) 可以通过此题。

int f[3000][3000];
inline void In(){
    const int mod=1e9+7,inv=5e8+4;
    for_(i,1,2005){
        f[i][i]=i;
    }
    for_(i,2,2005){
        for_(j,1,i-1){
            f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod*inv%mod;
        }
    }
    int T=read();
    while(T--){
        int n=read(),m=read(),k=read();
        print(f[n][m]*k%mod,"\n");
    }
}