zoj 3905 Cake(状压dp)

本文主要是介绍zoj 3905 Cake(状压dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：zoj 3905 Cake

代码

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 805;struct State {int a, b;State (int a = 0, int b = 0): a(a), b(b) {}bool operator < (const State& u) const {if (b != u.b) return b > u.b;return a < u.a;}
}S[maxn];int N, dp[maxn], tmp[maxn];int solve () {memset(dp, 0, sizeof(dp));for (int i = 1; i <= N; i++) {memcpy(tmp, dp, sizeof(dp));for (int j = 1; j <= (i>>1); j++)dp[j] = max(dp[j], tmp[j-1] + S[i].a);}return dp[N>>1];
}int main () {int cas;scanf("%d", &cas);while (cas--) {scanf("%d", &N);for (int i = 1; i <= N; i++)scanf("%d%d", &S[i].a, &S[i].b);sort(S + 1, S + N + 1);printf("%d\n", solve());}return 0;
}

这篇关于zoj 3905 Cake(状压dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---