当前位置: 代码迷 >> 综合 >> HDU1248 寒冰王座(完全背包)
  详细解决方案

HDU1248 寒冰王座(完全背包)

热度:43   发布时间:2024-01-16 13:41:41.0

题意:

中文题不解释

要点:

就是个完全背包的水题变形,注意因为最后钱用不完,所以d数组一开始全赋值为0。


17160682 2016-05-15 14:06:34 Accepted 1248 0MS 1752K 528 B C++ seasonal
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int spend[3] = { 150,200,350 };
int d[10005];int dp(int v)
{memset(d, 0, sizeof(d));for (int i = 0; i <= v; i++)for (int j = 0; j < 3; j++){if (i>=spend[j]){d[i] = max(d[i], d[i - spend[j]] + spend[j]);}}return d[v];
}
int main()
{int t,n;scanf("%d", &t);while (t--){scanf("%d", &n);printf("%d\n", n-dp(n));}return 0;
}