有点难，豆包写的，不要怪我拿下第一个通过

原题链接：21585.循环的债务

༺ཌༀ༒◈78千金羽91◈༒ༀ༻

2026-08-18 14:50:47

发布于：江苏

13阅读

0回复

0点赞

#include <bits/stdc++.h>
using namespace std;
const int MAXSUM = 1000;
const int INF = -1e9;

int val[] = {100,50,20,10,5,1};

int main(){
int x1,x2,x3;
cin>>x1>>x2>>x3;
// net: >0应该收钱，<0应该出钱
int netA = -x1 + x3;
int netB = x1 - x2;
int netC = x2 - x3;

int a[6],b[6],c[6];
for(int i=0;i<6;i++) cin>>a[i];
for(int i=0;i<6;i++) cin>>b[i];
for(int i=0;i<6;i++) cin>>c[i];

// 计算每个人初始总钱
int sa=0,sb=0,sc=0;
int total_notes=0;
for(int i=0;i<6;i++){
    sa += a[i]*val[i];
    sb += b[i]*val[i];
    sc += c[i]*val[i];
    total_notes += a[i]+b[i]+c[i];
}
int fa = sa + netA;
int fb = sb + netB;
int fc = sc + netC;
if(fa<0 || fb<0 || fc<0){
    cout<<"impossible\n";
    return 0;
}

// dp[moneyA][moneyB] = max keep
vector<vector<int>> dp(MAXSUM+1, vector<int>(MAXSUM+1, INF));
dp[0][0] = 0;

for(int idx=0;idx<6;idx++){
    vector<vector<int>> ndp(MAXSUM+1, vector<int>(MAXSUM+1, INF));
    int va = val[idx];
    int ta = a[idx], tb = b[idx], tc = c[idx];
    int tot = ta+tb+tc;
    // pa:给A张数，pb给B；pc=tot-pa-pb给C
    for(int pa=0;pa<=tot;pa++){
        for(int pb=0;pb+pa<=tot;pb++){
            int pc = tot - pa - pb;
            int keep = min(ta,pa)+min(tb,pb)+min(tc,pc);
            int addA = pa*va;
            int addB = pb*va;
            // 滚动dp
            for(int sumA=0;sumA+addA<=MAXSUM;sumA++){
                for(int sumB=0;sumB+addB<=MAXSUM;sumB++){
                    if(dp[sumA][sumB] == INF) continue;
                    ndp[sumA+addA][sumB+addB] = max(ndp[sumA+addA][sumB+addB], dp[sumA][sumB]+keep);
                }
            }
        }
    }
    dp.swap(ndp);
}

int max_keep = dp[fa][fb];
if(max_keep < 0){
    cout<<"impossible\n";
}else{
    cout << (total_notes - max_keep) << endl;
}
return 0;

}

有帮助，赞一个