【1】做题心得 - 2025 NOIP #33 - T2【动态规划】【高精度】

ExFish · 2025-09-06 14:52:46 · 题解

题目大意：n 个球可以放在前 a_i 个位置，选不超过 m 个球，贡献是一个箱子内没有两个球的方案数，并且我们不能选择距离 <k 的两个球。求最大贡献。

思路：注意到贡献是好求的。将所选 a_i 排序，贡献就是 \prod_{i=1}^m(a_i-i+1)。也就是剩余 a_i-i+1 个位置给第 i 号球放。然后我们考虑 dp。设 f_{i,\text{S}} 为前 i 个球，相对考虑位置所选集合 \text{S}。那么当 \text{S} \notin l 时，有转移 f_{i,\text{S}\cup l}=\max(f_{i,\text{S}\cup l},f_{\max(0,i-k),\text{S}}\times(a_i-l+1))，也就是考虑选择 a_i。

注意到答案范围是 <10^{9m} 的，也就是 10^{90} 数量级，就需要用卡常高精度，常数 \mathcal O(10)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=(1<<10)+1;
const int ydN=15,P=1e9;
struct ib{
    #define ll long long
    ll a[ydN];
    ib(){
        for(int i=1;i<=10;i++)
            a[i]=0;
    }
}res;
ib Mul(ib x,int y){
    ib z=ib();
    for(int i=1;i<=10;i++){
        z.a[i]+=x.a[i]*y;
        z.a[i+1]+=z.a[i]/P;
        z.a[i]%=P;
    }
    return z;
}
ib Max(ib x,ib y){
    for(int i=10;i;i--){
        if(x.a[i]>y.a[i])
            return x;
        else if(x.a[i]<y.a[i])
            return y;
    }
    return x;
}
ib f[N][M];
void Print(ib x){
    bool zero=0;
    for(int i=10;i;i--){
        if(zero)
            printf("%09d",x.a[i]);
        else if(x.a[i])
            zero=1,
            printf("%d",x.a[i]);    
    }
    return;
}
void maxs(ib &x,ib y){
    x=Max(x,y);
    return;
}
int n,m,k,a[N];
int main(){
    freopen("ball.in","r",stdin);
    freopen("ball.out","w",stdout);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[0][0].a[1]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<(1<<m);j++)
            f[i][j]=f[i-1][j];
        for(int j=0;j<(1<<m);j++){
            for(int l=0;l<min(m,a[i]);l++){
                int w=(j>>l)&1;
                if(!w)
                    maxs(f[i][j|(1<<l)],Mul(f[max(0,i-k)][j],a[i]-l));
            }
        }
    }
    res=ib();
    for(int i=1;i<=m;i++)
        maxs(res,f[n][(1<<i)-1]);
    Print(res);
    return 0;
}