又是 DP

zjd2013 · 2026-03-07 21:42:04 · 题解

link

Solution

在 上一篇题解 里，我用了两次背包 dp 过了这一题，这次我会用另一个方法。

考虑枚举钞票。500，200 欧元的个数不能确定，具体证明请看上一篇题解，hack：1004。对于其它的钞票，1,5,10,50,100 的个数最多是 1，如果个数大于一，用 2,10,20,100,200 更优，有时还能把个数变成奇数。2,20 的个数最多是 4，如果个数大于四，用 10,100 更优，同理，有时能把个数变成奇数。

枚举完，用多重背包判断是否可以分。

Code

:::success[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18,maxn=1e4+1;
const i128 Inf=1e35;
ll n,dp[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int e500=0;e500*500<=n;e500++)
    {
        for(int e200=0;e200*200+e500*500<=n;e200++)
        {
            for(int e100=0;e100<=1;e100++)
            {
                for(int e50=0;e50<=1;e50++)
                {
                    for(int e20=0;e20<=4;e20++)
                    {
                        for(int e10=0;e10<=1;e10++)
                        {
                            for(int e5=0;e5<=1;e5++)
                            {
                                for(int e2=0;e2<=4;e2++)
                                {

                                    for(int e1=0;e1<=1;e1++)
                                    {
                                        if(e500*500+e200*200+e100*100+e50*50+e20*20+e10*10+e5*5+e2*2+e1!=n) continue;
                                        memset(dp,0,sizeof(dp));
                                        for(int i=1;i<=9;i++)
                                        {
                                            ll v,w;
                                            if(i==1) v=500,w=e500;
                                            if(i==2) v=200,w=e200;
                                            if(i==3) v=100,w=e100;
                                            if(i==4) v=50,w=e50;
                                            if(i==5) v=20,w=e20;
                                            if(i==6) v=10,w=e10;
                                            if(i==7) v=5,w=e5;
                                            if(i==8) v=2,w=e2;
                                            if(i==9) v=1,w=e1;
                                            for(int j=1;j<=w;j++)
                                            {
                                                for(int k=n/2;k>=1;k--)
                                                {
                                                    if(k-v>=0) dp[k]=max(dp[k],dp[k-v]+v);
                                                }
                                            }
                                        }
                                        if(dp[n/2]*2!=n)
                                        {
                                            cout<<e500+e200+e100+e50+e20+e10+e5+e2+e1<<"\n";
                                            for(int i=1;i<=e500;i++) cout<<"500 ";
                                            for(int i=1;i<=e200;i++) cout<<"200 ";
                                            for(int i=1;i<=e100;i++) cout<<"100 ";
                                            for(int i=1;i<=e50;i++) cout<<"50 ";
                                            for(int i=1;i<=e20;i++) cout<<"20 ";
                                            for(int i=1;i<=e10;i++) cout<<"10 ";
                                            for(int i=1;i<=e5;i++) cout<<"5 ";
                                            for(int i=1;i<=e2;i++) cout<<"2 ";
                                            for(int i=1;i<=e1;i++) cout<<"1 ";
                                            return 0;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<"splittable";
}

:::