首页 > 代码库 > BZOJ2101 [Usaco2010 Dec]Treasure Chest 藏宝箱
BZOJ2101 [Usaco2010 Dec]Treasure Chest 藏宝箱
水水更健康。。。话说蒟蒻的noip爆炸了怎么办？←_←
这道题裸的区间dp：
f[i, j]表示当前取全了i到j之间的金币，最大值为多少
于是f[i, j] = sum[i, j] - min(f[i + 1, j], f[i, j - 1])
但是卡空间。。
于是改一下方程：
令len = j - i + 1，则
f[i, len]表示当前取全了i到i + len - 1之间的金币，最大值为多少
len从1开始向上枚举，于是第二维就可以压掉了。
然后就没有然后了= =
1 /************************************************************** 2 Problem: 2101 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:100 ms 7 Memory:844 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cctype>12 #include <algorithm>13 14 using namespace std;15 const int N = 5005;16 17 int s[N], f[N];18 int n;19 20 inline int read(){21 int x = 0;22 char ch = getchar();23 while (!isdigit(ch))24 ch = getchar();25 while (isdigit(ch)){26 x = x * 10 + ch - ‘0‘;27 ch = getchar();28 }29 return x;30 }31 32 int main() {33 n = read();34 int i, len;35 for (i = 1; i <= n; ++i) {36 f[i] = read();37 s[i] = s[i - 1] + f[i];38 }39 for (len = 1; len < n; ++len)40 for (i = 1; i <= n - len; ++i)41 f[i] = s[i + len] - s[i - 1] - min(f[i], f[i + 1]);42 printf("%d\n", f[1]);43 return 0;
BZOJ2101 [Usaco2010 Dec]Treasure Chest 藏宝箱
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。