淘宝做导航网站有哪些功能吗,网页设计网站首页代码,会计公司网站模板下载,phpcms做的网站有哪些这个题个人认为是我目前所做的最难的区间dp了#xff0c;以前把环变成链的方法在这个题上并不能使用#xff0c;因为那样可能存在重复计算 我第一遍想的时候就是直接把环变成链了#xff0c;wa了5个点#xff0c;然后仔细思考一下就发现了问题 比如这个样例 5 4 1 2 4 1 1 …这个题个人认为是我目前所做的最难的区间dp了以前把环变成链的方法在这个题上并不能使用因为那样可能存在重复计算 我第一遍想的时候就是直接把环变成链了wa了5个点然后仔细思考一下就发现了问题 比如这个样例 5 4 1 2 4 1 1 这个样例变成链以后就是这样 1 2 4 1 1 1 2 4 1 1 在这个链上很明显取[2,3]和[7,8]是最优方案答案是8但是很容易可以算出这个样例真正答案是7241。 因此这个方法是不可行的我在查阅了网上唯一的题解发现这个问题可以灰常巧妙的用初始赋值来解决我们可以进行两遍递推第一遍认为第一个点不可以被加进答案第二遍认为第二个点可以被加进答案 第一遍非常好理解是基于不考虑时间成环的第二个有点难想假如第一个点能选则说明至少在原序列终点及以前以前有个点是卖萌开始的起始点 那么我们处理的时候会认为在原序列上从真实的起始点一直到最后原序列终点被选了 比如这个样例 5 3 5 1 1 1 3 1 0 0 1 1 0为未选择1为选择 答案是8第二遍递推会认为1-1,4-5这两个区间合起来是答案就是这样来保证正确性的。 #includeiostream
#includecstdio
using namespace std;
int n,m,dp[2][3610][2],qwq[7210],ans,t;
inline void init()
{for(int j0;jm;j)dp[0][j][0]dp[0][j][1]dp[1][j][0]dp[1][j][1]-1e9;
}
void dp1()
{t0;for(int i2;in;i){t1-t;for(int j0;jm;j){dp[t][j][0]max(dp[1-t][j][0],dp[1-t][j][1]);if(j0)dp[t][j][1]max(dp[1-t][j-1][0],dp[1-t][j-1][1]qwq[i]);}}
}
int main()
{scanf(%d%d,n,m);if(m1)//特判一下如果卖萌时间就给了1或0答案一定为0 {printf(0);return 0;}for(int i1;in;i)scanf(%d,qwq[i]);init();//预处理需要用滚动数组优化时间 dp[0][1][1]dp[0][0][0]0;//当没有从最后一个位置开始的时候第一个时段答案肯定为0 dp1();ansmax(dp[t][m][0],dp[t][m][1]);//在最后时段取与不取之间找个最大值 init();dp[0][1][0]dp[0][1][1]qwq[1];//当从最后一个时段开始的时候 dp1();//进行两遍递推 ansmax(ans,dp[t][m][1]);printf(%d,ans);
} 转载于:https://www.cnblogs.com/Loi-dfkdsmbd/articles/7717383.html
