01
04[和最大上升子序] E - Super Jumping! Jumping! Jumping!
题目:
给定n个数字,选出一组递增子序列,使得和最大
分析:
把最长上升子序的递推公式改成求和
代码:
#include <bits/stdc++.h> using namespace std; int n; int a[1010]; int dp[1010]; void work() { // cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i], dp[i] = a[i]; int ans = 0; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j < i; j ++ ) if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + a[i]); ans = max(ans, dp[i]); } cout << ans << endl; } int main() { while (cin >> n, n) { work(); } return 0; }
05 [完全背包求体积恰好为m的最小值] F - Piggy-Bank
题目:
如标签一样,完全背包求提及恰好为m的最小值
分析:
注意初始化,dp[0] = 0, 其他的都是无穷大,这样答案只能从0转移来,不会从其他的地方转移而来
代码:
#include <bits/stdc++.h> using namespace std; int n, m, mm, mmm; int dp[10005]; void work() { //使填装背包的体积恰好为m,且价值最低 cin >> mm >> mmm; m = mmm - mm; cin >> n; memset(dp, 0x3f, sizeof dp); dp[0] = 0; int w, v; for (int i = 1; i <= n; i ++ ) { cin >> w >> v; for (int j = v; j <= m; j ++ ) dp[j] = min(dp[j], dp[j - v] + w); } if (dp[m] != 0x3f3f3f3f) printf("The minimum amount of money in the piggy-bank is %d.\n", dp[m]); else puts("This is impossible."); } int main() { int t; cin >> t; while (t -- ) work(); return 0; }