P14266 [ROI 2015 Day2] 保护野生动物

无钩七不改名 · 2026-11-11 16:12:06 · 题解

好久没写题解了啊……上次写题解居然已经是去年了。

数位 DP。

设 dp[i][j] 表示处理到第 i 位，进位为 j 时所能获得的最大目标资助金额。并记录从哪里转移过来，方便最后分配金额。

注意到 j 只会是 0\sim2。因为当上一位进位为 1 且这一位三个数都为 1 时，进位为 2，当上一位进位为 2 且这一位三个数都为 1 时，进位也为 2，故最大进位为 2。

转移方式为：枚举有多少个数这一位为 1 和进位数，获得新的当前位和进位，若当前位等于 n 在二进制下的该位，则转移。设当前位为 i，如果 3 个数这一位全为 1，则当前位贡献 2^i 给目标资助。

令二进制下 n 的最高位为 L，则答案为 dp[L][0]，只需要倒推获得每个机构能获得的金额即可。

code：

#include<bits/stdc++.h>
using namespace std;

const int N=65;

int T;
long long n,dp[N][3],ans[4];
pair<int,int> p[N][3];

long long read(){
    long long k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        k=k*10+ch-'0';
        ch=getchar();
    }
    return k;
} 

int main(){
    T=read();
    while(T--){
        n=read();
        memset(dp,0xcf,sizeof dp);
        if(n&1){
            dp[0][0]=0;
            p[0][0]={1,0};
            dp[0][1]=1;
            p[0][1]={3,0};
        }
        else{
            dp[0][0]=0;
            p[0][0]={0,0};
            dp[0][1]=0;
            p[0][1]={2,0};
        }
        n>>=1;
        int L=0;
        while(n){
            int nw=(n&1);
            n>>=1;
            ++L;
            for(int i(0);i<=3;++i){
                for(int j(0);j<=2;++j){
                    if(((i+j)&1)!=nw)continue;
                    long long val=dp[L-1][j]+(i==3)*(1ll<<L);
                    if(val>dp[L][(i+j)/2]){
                        dp[L][(i+j)/2]=val;
                        p[L][(i+j)/2]={i,j};
                    }
                }
            }
        }
        ans[1]=0;ans[2]=0;ans[3]=0;
        for(int i(L),nw(0);i>=0;--i){
        //  cout<<i<<" p[i][nw] "<<p[i][nw].first<<" "<<p[i][nw].second<<'\n';
            for(int j(p[i][nw].first);j;--j)ans[j]+=(1ll<<i);
            nw=p[i][nw].second;
        }
        printf("%lld %lld %lld\n",ans[1],ans[2],ans[3]);
    }
    return 0;
}