codeforces George and Job
生活随笔
收集整理的這篇文章主要介紹了
codeforces George and Job
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1 /*
2 題意：給一個長度為n的序列， 從中選擇長度為m的k個區(qū)間（任意兩個區(qū)間不會有公共部分）
3 使得所選擇的區(qū)間的和最大！
4 思路：這是一種很常見的dp
5
6 dp[i][j] 表示的是前 i 個數(shù)選擇 j 個 長度為m區(qū)間的最大和！
7 s[i]記錄的是前 i 個數(shù)字的和！
8 dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );
9 */
10 #include<iostream>
11 #include<cstdio>
12 #include<cstring>
13 #include<algorithm>
14 #define N 5005
15 using namespace std;
16 typedef long long ll;
17
18 ll dp[N][N];
19 ll s[N];
20
21 int main(){
22 int n, m, k;
23 scanf("%d%d%d", &n, &m, &k);
24 for(int i = 1; i <= n; ++i){
25 scanf("%lld", &s[i]);
26 s[i] += s[i-1];
27 }
28
29 for(int j = 1; j <= k; ++j)
30 for(int i = j*m; i <= n; ++i)
31 dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );
32
33 printf("%lld\n", dp[n][k]);
34
35 return 0;
36 }
題意： 給定2個字符串a(chǎn), b，求b的子序列在a中出現(xiàn)的次數(shù)。要求可以是不連續(xù)的，但是b在a中的順序必須和b以前的一致。 思路： dp[i][j]表示：b的前j個字符在a的前i個字符中出現(xiàn)的次數(shù)。 似乎這種表示方法司空見慣，但是一開始我還真沒能搞懂如何去遞推。事情的真相是： 如果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];
?
附一個經(jīng)典的dp！題意： 給定2個字符串a(chǎn), b，求b的子序列在a中出現(xiàn)的次數(shù)。要求可以是不連續(xù)的，但是b在a中的順序必須和b以前的一致。 思路： dp[i][j]表示：b的前j個字符在a的前i個字符中出現(xiàn)的次數(shù)。 似乎這種表示方法司空見慣，但是一開始我還真沒能搞懂如何去遞推。事情的真相是： 如果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];
?
轉載于:https://www.cnblogs.com/hujunzheng/p/3991460.html
總結
以上是生活随笔為你收集整理的codeforces George and Job的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何选购适合自己的房子？
- 下一篇： 请问下塔吊司机年审需要什么资料啊