codeforces George and Job

简介:

/*
    题意:给一个长度为n的序列, 从中选择长度为m的k个区间(任意两个区间不会有公共部分)
    使得所选择的区间的和最大!
    思路:这是一种很常见的dp
    
    dp[i][j] 表示的是前 i 个数选择 j 个 长度为m区间的最大和! 
    s[i]记录的是前 i 个数字的和! 
    dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5005
using namespace std;
typedef long long ll;

ll dp[N][N];
ll s[N];

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &s[i]);
        s[i] += s[i-1];
    }
    
    for(int j = 1; j <= k; ++j)
        for(int i = j*m; i <= n; ++i)
           dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );
           
    printf("%lld\n", dp[n][k]);
    
    return 0; 
}


附一个经典的dp!

题意:
给定2个字符串a, b,求b的子序列在a中出现的次数。要求可以是不连续的,但是b在a中的顺序必须和b以前的一致。
思路:
dp[i][j]表示:b的前j个字符在a的前i个字符中出现的次数。
似乎这种表示方法司空见惯,但是一开始我还真没能搞懂如何去递推。事情的真相是:
如果a[i] == b[j]则 dp[i][j] = dp[i-1][j] + dp[i-1][j-1];

如果a[i] != b[j]则 dp[i][j] = dp[i-1][j];

目录
相关文章
codeforces 339A.Helpful Maths B.Xenia and Ringroad 两水题
.题意就是把字符串里面的数字按增序排列,直接上代码。
39 0
AtCoder Beginner Contest 226 E - Just one(dfs求连通块 组合数学)
AtCoder Beginner Contest 226 E - Just one(dfs求连通块 组合数学)
104 0
|
人工智能 Windows
Educational Codeforces Round 113 (Rated for Div. 2) C - Jury Meeting (思维 组合数)
Educational Codeforces Round 113 (Rated for Div. 2) C - Jury Meeting (思维 组合数)
97 0
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
115 0
|
机器学习/深度学习 人工智能 BI
Educational Codeforces Round 115 (Rated for Div. 2) D. Training Session(组合数学 思维)
Educational Codeforces Round 115 (Rated for Div. 2) D. Training Session(组合数学 思维)
107 0
POJ-2488,A Knight's Journey(DFS)
POJ-2488,A Knight's Journey(DFS)
HDOJ/HDU 1241 Oil Deposits(经典DFS)
HDOJ/HDU 1241 Oil Deposits(经典DFS)
86 0
【1087】All Roads Lead to Rome (30 分)
【1087】All Roads Lead to Rome (30 分) 【1087】All Roads Lead to Rome (30 分)
118 0