题目
考点 dp+前缀和+贪心
思路：
- 这题简单看起来是个dp问题，做的主要难点是找不到的条件，dp数组不会写，开始想用dp[i][j]来枚举左右端点，但是其实i和j有关，就可以将和背包问题一样，将i看作背包的容积，m看作物品的体积，最后的k是物品的种类。
- 主要的难点是加了一个贪心的思想，就是虽然区间可以是i+0~i+m但是每个区间都要尽可能大，不会因为前面的区间影响后面区间的选择，这是难点。
代码如下：
点击查看代码
/*
程序名:.cpp
功能:
作者:王铭硕
日期：2021.
*/
#include
#define ll long long
#define cin(x) scanf("%d",&x)
#define cout(x) printf("%d",x)
#define cinll(x) scanf("%lld",&x)
#define coutll(x) printf("%lld",x)
#define pb(x) push_back(x)
using namespace std;
ll w[5010],res[5010],a[5010],dp[5010][100000];
int main(){
ll n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
res[i]=res[i-1]+a[i];
}
ll x=0;
for(int i=1;(i+m-1)<=n;i++){
w[++x]=res[i+m-1]-res[i-1];
}
for(int i=1;i<=x;i++){
for(int j=1;j<=k;j++){
if(i
总结：这题的主要难点就是想到那个贪心的思想，前面的区间再大，也不会影响后面区间的值。