站长之家ip查询,微平台公众号,宁波做网站gs,公司网站友情链接题目链接 90 Points#xff1a;智障的区间 DP……设 dp[i][j] 表示区间 [i, j] 能取的最大价值#xff0c;但我还是 sd 地开了第三维表示先取还是后取的价值。 交上去以为能 A#xff0c;结果 #2 开心地 MLE……一看内存#xff0c;64MB#xff08;把评测机吊起来打一顿智障的区间 DP……设 dp[i][j] 表示区间 [i, j] 能取的最大价值但我还是 sd 地开了第三维表示先取还是后取的价值。 交上去以为能 A结果 #2 开心地 MLE……一看内存64MB把评测机吊起来打一顿…… 100 Points有些神仙……区间 DP 的滚动数组dp[i] 表示以 i 为首的区间得到的最大价值。 换一种思路定义 dp[l][r] 为在区间 [l,r] 先手的人能取到的最大值区间的长度每加 1先手就会互换一次为了让这一次的先手更大就要让上一次更小于是得到 $ dp[l][r] sum[r] - sum[l - 1] - min(dp[l][r - 1], dp[l 1][r]); $ 斜着滚掉一维……dp[i] 为从 i 到 i l - 2 区间最优解 $ dp[i] sum[j] - sum[i - 1] - min(dp[i], dp[i 1]); $ 放上代码。 90 分 #include queue
#include cstdio
#include cctype
#include cstring
#include iostream
#include algorithm
using namespace std;const int maxn 5000 10;
int n, c[maxn], dp[maxn][maxn][2];int main(int argc, const char *argv[])
{freopen(..\\nanjolno.in, r, stdin);freopen(..\\nanjolno.out, w, stdout);scanf(%d, n);for(int i 1; i n; i) scanf(%d, c[i]), dp[i][i][0] c[i];for(int i 1; i n; i)dp[i][i 1][0] max(c[i], c[i 1]), dp[i][i 1][1] min(c[i], c[i 1]);for(int i 3; i n; i) {for(int l 1; l n - i 1; l) {int r l i - 1;if( c[l] dp[l 1][r][1] c[r] dp[l][r - 1][1] )dp[l][r][0] c[l] dp[l 1][r][1], dp[l][r][1] dp[l 1][r][0];else dp[l][r][0] c[r] dp[l][r - 1][1], dp[l][r][1] dp[l][r - 1][0];}}printf(%d %d\n, dp[1][n][0], dp[1][n][1]);fclose(stdin), fclose(stdout);return 0;
} 100 分 #include queue
#include cstdio
#include cctype
#include cstring
#include iostream
#include algorithm
using namespace std;const int maxn 5000 10;
int n, c[maxn], dp[maxn];int main(int argc, const char *argv[])
{freopen(..\\nanjolno.in, r, stdin);freopen(..\\nanjolno.out, w, stdout);scanf(%d, n);for(int i 1; i n; i) scanf(%d, dp[i]), c[i] c[i - 1] dp[i];for(int i 2; i n; i) {for(int l 1; l n - i 1; l) {int r l i - 1;dp[l] c[r] - c[l - 1] - min(dp[l], dp[l 1]);}}printf(%d\n, dp[1]);fclose(stdin), fclose(stdout);return 0;
} —— 月光 委身依赖 红莲 彻骨清明 残留余韵 是抗争 徒留其名 转载于:https://www.cnblogs.com/nanjoqin/p/10090619.html
