Codeforces Round #267 (Div. 2) C George and Job_html/css_WEB-ITnose

The main idea of ​​the question: Select m disjoint substrings from n numbers. The length of the substrings is all k. Ask what is the maximum sum of all the numbers in all the selected substrings.

For the DP question, DP is still too weak. The dp equation at the beginning was actually written as O(n^3)...

dp[i][j]: in num The sequence at the end of [i] is divided into the maximum sum of j segments

dp[i][j]=max(dp[k][j-1] sum[i]-sum[i-m]) In this case , in fact, as long as the first loop is the number of selected segments, the number of numbers in the second loop

I changed my mind again

dp[i][j]: the first i numbers , the maximum sum divided into j segments

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

Thinking: It’s two-dimensional, so the written dp equation must be either transferred from the change in the first dimension, or transferred from the change in the second dimension

AC code:

//#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <iostream>#include <iomanip>#include <cmath>#include <map>#include <set>#include <queue>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<e;i++)#define repe(i,s,e) for(int i=s;i<=e;i++)#define CL(a,b) memset(a,b,sizeof(a))#define IN(s) freopen(s,"r",stdin)#define OUT(s) freopen(s,"w",stdout)const ll ll_INF = ((ull)(-1))>>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 code for the first idea (extracted from http://blog.csdn.net/qian99/article/details/ 39397101):

#include<iostream>  #include<cstdio>  #include<cstring>  #include<string>  #include<algorithm>  #include<map>  #include<queue>  #include<stack>  #include<set>  #include<cmath>  #include<vector>  #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;  }