[USACO03FALL] Cow Exhibition G - 洛谷

曲折经过

爆搜

一开始没什么好的想法，就针对每头奶牛去or不去进行了爆搜。

#include 
#include 
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 
#include 
#include 
using namespace std;
#define maxn 405
#define maxm 2005
int 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 
  #include 
  #include 
  using namespace std;
  #define maxn 405
  #define maxm 2005
  int 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;
  }