[USACO03FALL] Cow Exhibition G - 洛谷
曲折經過
爆搜
一開始沒什么好的想法，就針對每頭奶牛去or不去進行了爆搜。
#include <cstdio>
#include <algorithm>
using namespace std;#define maxn 405
int iq[maxn], eq[maxn];
int ans;
int n;void dfs(int k, int sumiq, int sumeq) {//printf("k:%d,sumiq %d, sumeq %d\n", k, sumiq, sumeq);if (k == n + 1) {if (sumiq < 0 | sumeq < 0) {return;}ans = max(ans, sumiq + sumeq);return;}dfs(k + 1, sumiq + iq[k], sumeq + eq[k]);dfs(k + 1, sumiq, sumeq);
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d %d", &iq[i], &eq[i]);}dfs(1, 0, 0);printf("%d\n", ans);return 0;
}但這代碼交上去有5個數據點T了，所以還是得想其他的辦法，比如DP。?
二維DP
一開始設計了一個三維的狀態，f[i][j][k]表示到第i頭牛，智商和為j，情商和為k時的情商與智商和。
但這數組有點太大了...
考慮到j，k兩維的下標其實與數組值有一定關系，所以我們優化掉第三維，把狀態改成f[i][j]表示到第i頭牛，智商和為j時的情商和。
又考慮到，智商和、情商和可能取到負數，為了保證數組下標的合法性，我們對數組下標整體進行了偏移。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;#define maxn 405
#define maxm 2005int iq[maxn], eq[maxn];
int ans, n;
int dp[maxn][maxm * maxn];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d %d", &iq[i], &eq[i]);}memset(dp, -0x3f, sizeof(dp));dp[0][400000] = 0;for (int i = 1; i <= n; i++) {//合理調整dp邊界if (iq[i] >= 0) {for (int j = iq[i]; j <= 800000; j++) {//for (int j = 800000; j >= iq[i]; j--) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - iq[i]] + eq[i]);//printf("dp[%d][%d]:%d\n", i, j, dp[i][j]);}} else {for (int j = 0; j <= 800000 + iq[i]; j++) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - iq[i]] + eq[i]);//printf("dp[%d][%d]:%d\n", i, j, dp[i][j]);}}}for (int j = 400000; j <= 800000; j++) {//智商和不能為負//printf("%d\n", dp[n][j] + j - 400000);if (dp[n][j] > 0)//情商和不能為負ans = max(ans, dp[n][j] + j - 400000);}printf("%d\n", ans);return 0;
}?一些細節：
- dp數組初始化成很小的數而非0，因為情商和有可能取負數
- dp[0][400000]=0，偏移后的數組400000相當于零坐標，是合法狀態
- dp邊界的處理
- 找答案時的處理，且注意答案對應的是dp[n][j]+j，再減去總體偏移量400000
但MLE..
正解
一維DP
利用滾動數組優化
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;#define maxn 405
#define maxm 2005int iq[maxn], eq[maxn];
int ans, n;
int dp[maxm * maxn];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d %d", &iq[i], &eq[i]);}memset(dp, -0x3f, sizeof(dp));dp[400000] = 0;for (int i = 1; i <= n; i++) {if (iq[i] >= 0) {for (int j = 800000; j >= iq[i]; j--) {dp[j] = max(dp[j], dp[j - iq[i]] + eq[i]);//printf("dp[%d][%d]:%d\n", i, j, dp[i][j]);}} else {for (int j = 0; j <= 800000 + iq[i]; j++) {dp[j] = max(dp[j], dp[j - iq[i]] + eq[i]);//printf("dp[%d][%d]:%d\n", i, j, dp[i][j]);}}}for (int j = 400000; j <= 800000; j++) {//printf("%d\n", dp[n][j] + j - 400000);if (dp[j] > 0)ans = max(ans, dp[j] + j - 400000);}printf("%d\n", ans);return 0;
}?
