题目描述
怎么硕呢,老师考试出的新题,自己灵光一闪想出来的思路,但下来老师看了说我的思路不正统(直接炸掉)。
洛谷上提交不了了,那就来acwing上试试有没有人能看懂本蒟蒻的奇葩思路吧。
思路
f[i][j]定义:右端点为i,选择长度为j的连续牛序列的价值,并且前面有选择其他连续的牛序列时也会累加转移到后面
C++ 代码
#include <bits/stdc++.h>
using namespace std;
long long f[2][100010],w[100010];
int n,m;
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
cin>>w[i];
cnt+=w[i];//为特判做准备
}
if(m==1)
{
cout<<cnt;
return 0;
}//特判:如果长度为一,则直接加上所有价值就好
for(int i=1;i<=n;i++)//遍历右节点
{
for(int j=0;j<=m&&j<=i;j++)//0代表不选,其余的是连续选择的长度
{
if(j>=1)f[i&1][j]=f[(i-1)&1][j-1]+w[i];//j不为零的时候可以从j-1转移(包括j-1=0时)
f[i&1][0]=max(f[i&1][0],f[(i-1)&1][j]);
//f[i][0]可从f[i-1][0]与f[i-1][j]转移,上一个可以不选,可以选任意一个长度
//用了滚动数组因为范围实在是太大了
}
}
long long maxx=0;
for(int i=0;i<=m;i++)
{
maxx=max(maxx,f[n&1][i]);//最后一个也可以选,而且可以是这次选择的第任意个牛
}
cout<<maxx;
return 0;
}
OS:
emm,acwing会因为时间卡掉四个点,但洛谷上没有问题,但感觉思路很好懂,所以发在题解上,本蒟蒻第一篇题解,不喜勿喷QAQ