HDU 1244 Max Sum Plus Plus Plus - dp

전송문

제목 대의:

서열을 주십시오. 서열을 m단으로 나누어 왼쪽에서 오른쪽으로 각각 l1, l2,...lm, 가장 큰 합이 얼마인지 구하세요.

제목 분석:

최대 m 세그먼트와 유사합니다. 먼저\(i\in[1,m]\)를 열거한 다음 $j\in[num], n] $, dp를\[dp[j][i] = max(dp[j-1] [i], dp[j-num[i]] [i] [i-1] + sum[j] - sum[i-num[i]]]]]로 옮깁니다.\]

code:

#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

const int N = 1005, M = 25;
int n, m, num[N];
typedef long long ll;
ll sum[N], f[N][N];

inline int read(){
    ll i = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(ll x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
}

int main(){
    while(n = read()){
        m = read();
        sum[0] = 0;
        for(int i = 1; i <= m; i++) num[i] = read();
        for(int i = 1; i <= n; i++){
            ll x = read() * 1LL;
            sum[i] = sum[i - 1] + x;
        }
        int now = 0;
        for(int i = 1; i <= m; i++){
            now += num[i];
            for(int j = now; j <= n; j++)
                f[j][i] = max(f[j - 1][i], f[j - num[i]][i - 1] + sum[j] - sum[j - num[i]]);
        }
        wr(f[n][m]), putchar('
');
    }
}

전재 대상:https://www.cnblogs.com/CzYoL/p/7659206.html