Codeforces ラウンド #267 (ディビジョン 2) C George と Job_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-1]+sum[i]-sum[i-m]) この場合、実際には、最初のループは選択されたセグメントの数、二重ループ中の数値の数です

また考えが変わりました

dp[i][j]: j 個のセグメントに分割された最初の i 数値の最大合計

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

思考: 2 次元なので、書かれた dp 方程式は 1 次元のものでなければなりません 変更は転送されるか、2 次元の変更から転送されます

AC コード:

//#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 コード (http:// から抜粋) blog.csdn.net/qian99/article/details/39397101):

rree