选取数对
给定一个长度为 n 的整数数列 a1,a2,…,an。
请你选择 k 个数对 [l1,r1],[l2,r2],…,[lk,rk],要求所选数对满足:
- 1≤l~1~≤r~1~<l~2~≤r~2~<…<l~k~≤r~k~≤n。
- 对于 1≤i≤k,ri−li+1=m 均成立。
请你输出 sum 的最大可能值。
输入格式
第一行包含三个整数 n,m,k。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数,表示 sum 的最大可能值。
数据范围
前 6 个测试点满足 1≤m×k≤n≤20。
所有测试点满足 1≤m×k≤n≤5000,0≤a~i~≤10^9^。
输入样例1:
5 2 1
1 2 3 4 5
输出样例1:
9
输入样例2:
7 1 3
2 10 7 18 5 33 0
输出样例2:
61
思路
闫式dp分析法
状态表示f[i][j]:表示在前i个数中选,j个区间的所有集合,属性:max
状态计算f[i][j]:根据最后一个区间是否包含最后一个点i来进行集合划分
1.不包含:f[i][j]=max(f[i][j],f[i-1][j])
2.包含:f[i][j]=max(f[i][j],f[i-m][j-1]+sum[i]-sum[i-m]) //如果包含i的话最后一个区间的右端点就是i
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5010;
typedef long long LL;
int a[N];
LL sum[N];
LL f[N][N];
int n,m,k;
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i]; //前缀和
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
f[i][j]=f[i-1][j];
if(i-m+1>=1){
LL num=f[i-m][j-1]+sum[i]-sum[i-m];
f[i][j]=max(f[i][j],num);
}
}
}
cout<<f[n][k]<<endl;
return 0;
}
神乎其技,dp学到家了
提个问,为啥遍历判断的那里是i-m+1,如果表示的是区间左端点必须为正整数的话,那比如说当i = 3,m = 2时,这时候的区间应该是【1,3】,那左端点不是i-m嘛,虽然知道这样不对,但是想不明白,求教!
题目给的条件是r-l+1=m对吧,我们是枚举的右端点,右端点是r=i,那么左端点就是l=i-m+1,我们下标是从1开始的,所以i-m+1>=1
r-l+1,表示的是从l到r一共有m个数,你上面举的那个例子,区间是2-3
啊!懂了,谢谢大佬!【比心】
orz
大佬nb
为啥f[i][j] = f[i-1][j]呢?
他表示的意思就是f[i][j]=max(f[i][j],f[i-1][j]),不选的意思,因为初始化都是0,所以一开始的时候f[i][j]肯定是小于等于f[i-1][j]的,所以直接不判断了,直接写了
正宗的DP啊
妙啊