CodeforcesRound#267(Div.2)CGeorgeandJob_html/css

来源：懂视网责编：小采时间：2020-11-27 15:55:36

CodeforcesRound#267(Div.2)CGeorgeandJob_html/css

CodeforcesRound#267(Div.2)CGeorgeandJob_html/css_WEB-ITnose:题目大意：从n个数中选出m段不相交的子串，子串的长度均为k，问所有选出来的子串的所有数的和最大为多少。 DP题，DP还是太弱，开始时的dp方程居然写成了O(n^3)... dp[i][j]: 以num[i]结尾的序列，分成j段的最大和 dp[i][j]=max(dp[k][j

推荐度：

点击下载本文 文档为doc格式

导读CodeforcesRound#267(Div.2)CGeorgeandJob_html/css_WEB-ITnose:题目大意：从n个数中选出m段不相交的子串，子串的长度均为k，问所有选出来的子串的所有数的和最大为多少。 DP题，DP还是太弱，开始时的dp方程居然写成了O(n^3)... dp[i][j]: 以num[i]结尾的序列，分成j段的最大和 dp[i][j]=max(dp[k][j

题目大意：从n个数中选出m段不相交的子串，子串的长度均为k，问所有选出来的子串的所有数的和最大为多少。

DP题，DP还是太弱，开始时的dp方程居然写成了O(n^3)...

dp[i][j]: 以num[i]结尾的序列，分成j段的最大和

dp[i][j]=max(dp[k][j-1]+sum[i]-sum[i-m]) 这样的话，其实只要第一重循环是选的段数，第二重循环时数字个数

我又换了种思路

dp[i][j]: 前i个数，分成j段的最大和

dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m])

思路：二维嘛，所以写出来的dp方程肯定是要么从第一维变化转移过来的，要么从第二维的变化转移过来的

AC代码：

//#pragma comment(linker, "/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i>1;const double EPS = 1e-8;const double pi = acos(-1);const int INF = 100000000;const int MAXN = 5000+100;ll num[MAXN],dp[MAXN][MAXN],pp[MAXN];int n,m,k;ll solve(){ CL(dp,0); for(int i=m;i<=n;i++) for(int j=1;j<=k;j++)  dp[i][j]=max(dp[i-m][j-1]+pp[i]-pp[i-m],dp[i-1][j]); return dp[n][k];}int main(){ //IN("C.txt"); while(~scanf("%d%d%d",&n,&m,&k)) { pp[0]=0; for(int i=1;i<=n;i++) {  scanf("%I64d",&num[i]);  pp[i]=pp[i-1]+num[i]; } printf("%I64d\n",solve()); } return 0;}

第一种思路的AC代码（摘自 http://blog.csdn.net/qian99/article/details/39397101）：

#include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define Inf 0x3FFFFFFFFFFFFFFFLL #define eps 1e-8 #define pi acos(-1.0) using namespace std; typedef long long ll; const int maxn = 5000 + 5; int a[maxn]; ll sum[maxn],dp[maxn][maxn],maxv[maxn]; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i = 1;i <= n;++i)  scanf("%d",&a[i]); sum[0] = 0; for(int i = 1;i <= n;++i)  sum[i] = sum[i-1] + a[i]; memset(dp,0xff,sizeof(dp)); memset(maxv,0,sizeof(maxv)); dp[0][0] = 0; for(int j = 1;j <= k;++j) {  for(int i = 1;i <= n;++i)  {  if(i - m >= 0)  {   dp[i][j] = max(dp[i][j],maxv[i-m] + sum[i] - sum[i-m]);  }  }  for(int i = 1;i <= n;++i)  maxv[i] = max(maxv[i-1],dp[i][j]); } ll ans = 0; for(int i = 1;i <= n;++i)  if(dp[i][k] != -1)  ans = max(ans,dp[i][k]); printf("%I64d\n",ans); return 0; }

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

CodeforcesRound#267(Div.2)CGeorgeandJob_html/css

推荐度：

点击下载本文 文档为doc格式

标签： and div round

热门焦点

CodeforcesRound#267(Div.2)CGeorgeandJob_html/css

CodeforcesRound#267(Div.2)CGeorgeandJob_html/css

CodeforcesRound#267(Div.2)CGeorgeandJob_html/css

最新推荐

猜你喜欢

热门推荐