菜鸟求助
  • 板块学术版
  • 楼主梦理乾坤
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/7/12 09:11
  • 上次更新2023/11/6 23:15:42
查看原帖
菜鸟求助
119552
梦理乾坤楼主2020/7/12 09:11

二维费用背包 潜水员这题 我总是输出250,应该是249 谢谢大佬帮我查一下,谢谢!!

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 10000;

#define C getchar()
inline void read(int& s)
{
    s     = 0;
    int t = 1, k = C;
    for (; k < '0' || k > '9'; k = C)
        if (k == '-')
            t = -1;
    for (; k >= '0' && k <= '9'; k = C)
        s = (s << 1) + (s << 3) + (k ^ 48);
    s *= t;
}
void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = ~(x - 1);
    }
    int s[20], top = 0;
    while (x)
    {
        s[++top] = x % 10;
        x /= 10;
    }
    if (!top)
        s[++top] = 0;
    while (top)
        putchar(s[top--] + '0');
    putchar('\n');
}

int f[N][N];

int main()
{
    int m, n, k;
    
    read(m);
    read(n);
    read(k);

    for (int i = 1; i <= k; i ++ )
    {
        int a, b, c;
        
        read(a);
        read(b);
        read(c);

        for (int j = m; j >= a; j -- )
            for (int d = n; d >= b; d -- )
                f[j][d] = max(f[j][d], f[j - a][d - b] + c);
    }

    write(f[m][n]);
    return 0;
}
2020/7/12 09:11
加载中...