代码有四个测试点是错的，有注释

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

悠悠磕到甲沟炎（李昊哲）

分支·分支解题者

2025-11-23 16:39:55

发布于：浙江

0阅读
0回复
0点赞

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;

const int MAX = 1005;
const int INF = 1e9;

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

int main() {
int x1, x2, x3;
cin >> x1 >> x2 >> x3;

int money[3][6];
int total_money[3] = {0};

// 读取钞票信息并计算总金额
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 6; j++) {
        cin >> money[i][j];
        total_money[i] += money[i][j] * denominations[j];
    }
}

// 计算目标金额
int target[3];
target[0] = total_money[0] + x3 - x1;
target[1] = total_money[1] + x1 - x2;
target[2] = total_money[2] + x2 - x3;

int total = total_money[0] + total_money[1] + total_money[2];

// 检查可行性
if (target[0] + target[1] + target[2] != total_money[0] + total_money[1] + total_money[2]) {
    cout << "impossible" << endl;
    return 0;
}

for (int i = 0; i < 3; i++) {
    if (target[i] < 0) {
        cout << "impossible" << endl;
        return 0;
    }
}

// 特殊情况：目标金额等于初始金额
if (target[0] == total_money[0] && target[1] == total_money[1] && target[2] == total_money[2]) {
    cout << 0 << endl;
    return 0;
}

// 使用状态压缩的DP
vector<vector<int>> dp(total + 1, vector<int>(total + 1, INF));
dp[total_money[0]][total_money[1]] = 0;

bool updated = true;
while (updated) {
    updated = false;
    for (int a = 0; a <= total; a++) {
        for (int b = 0; b <= total; b++) {
            int c = total - a - b;
            if (c < 0 || c > total) continue;
            
            if (dp[a][b] != INF) {
                // 尝试所有面额的转移
                for (int k = 0; k < 6; k++) {
                    int denom = denominations[k];
                    
                    // A给B
                    if (a >= denom && b + denom <= total) {
                        if (dp[a-denom][b+denom] > dp[a][b] + 1) {
                            dp[a-denom][b+denom] = dp[a][b] + 1;
                            updated = true;
                        }
                    }
                    // A给C
                    if (a >= denom) {
                        if (dp[a-denom][b] > dp[a][b] + 1) {
                            dp[a-denom][b] = dp[a][b] + 1;
                            updated = true;
                        }
                    }
                    // B给A
                    if (b >= denom && a + denom <= total) {
                        if (dp[a+denom][b-denom] > dp[a][b] + 1) {
                            dp[a+denom][b-denom] = dp[a][b] + 1;
                            updated = true;
                        }
                    }
                    // B给C
                    if (b >= denom) {
                        if (dp[a][b-denom] > dp[a][b] + 1) {
                            dp[a][b-denom] = dp[a][b] + 1;
                            updated = true;
                        }
                    }
                    // C给A
                    if (c >= denom && a + denom <= total) {
                        if (dp[a+denom][b] > dp[a][b] + 1) {
                            dp[a+denom][b] = dp[a][b] + 1;
                            updated = true;
                        }
                    }
                    // C给B
                    if (c >= denom && b + denom <= total) {
                        if (dp[a][b+denom] > dp[a][b] + 1) {
                            dp[a][b+denom] = dp[a][b] + 1;
                            updated = true;
                        }
                    }
                }
            }
        }
    }
}

if (dp[target[0]][target[1]] == INF) {
    cout << "impossible" << endl;
} else {
    cout << dp[target[0]][target[1]] << endl;
}

return 0;

}
有四个测试点是错的，谁要拿走就改一改吧

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论