题目大意：有一个小猪存钱罐，给出空和满时候的重量，并给出若干种面额的硬币大小和重量，个数不限，问装满小猪时，硬币最小总额是多少，若无法装满，输出impossible 解题思路：完全背包，dp 数组开小了 TLE 好几发……看了半天不知道哪里有问题 还以为会是越界什么的 居然是 TLE
#include<iostream> #include<stdio.h> #include<algorithm> #include<cmath> #include<string.h> #include<string> #include<queue> #include<map> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) const int INF = 0x3f3f3f3f; const int NINF = -INF -1; const int MAXN = 500+5; using namespace std; struct coin { int p, w; }; coin c[MAXN]; int dp[10005]; int T, E, F, val, n; int main() { scanf("%d", &T); while (T--) { memset(dp, 0, sizeof(dp)); scanf("%d%d", &E, &F); val = F - E; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &c[i].p, &c[i].w); for (int i = 0; i <= val; i++) dp[i] = INF; dp[0] = 0; for (int i = 0; i < n; i++) for (int j = c[i].w; j <= val; j++) dp[j] = min(dp[j], dp[j-c[i].w]+c[i].p); // for (int i = 0; i <= val; i++) // printf("%d\n", dp[i]); if (dp[val] == INF) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[val]); } return 0; }