题意描述
思路
使用
f
[
i
]
[
j
]
f[i][j]
f[i][j]来表示轮到选择第
i
i
i个数并且已经选择了
j
j
j个数时的最大
s
u
m
sum
sum值，得到状态转移方程：
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
k
]
[
j
−
1
]
+
a
[
i
]
)
,
i
−
m
≤
k
<
i
f[i][j]=max(f[i][j],f[k][j-1]+a[i]),i-m≤k<i
f[i][j]=max(f[i][j],f[k][j−1]+a[i]),i−m≤k<i 即从
[
i
−
m
,
i
)
[i-m,i)
[i−m,i)中找到已经选了
j
−
1
j-1
j−1个数时的最大值再加上
a
[
i
]
a[i]
a[i]，最后从
n
−
m
+
1
n-m+1
n−m+1遍历到
n
n
n，最大值即为答案。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
typedef unsigned long long ull
;
typedef pair
<int,int> PII
;
typedef pair
<long,long> PLL
;
typedef pair
<char,char> PCC
;
typedef long long ll
;
const int N
=205;
const int M
=1e6+10;
const int INF
=0x3f3f3f3f;
const int MOD
=1e9+7;
ll a
[N
],f
[N
][N
];
void solve(){
ll n
,m
,x
;cin
>>n
>>m
>>x
;
rep(i
,1,n
+1) cin
>>a
[i
];
if(n
/m
>x
) cout
<<-1<<endl
;
else{
ll lim
=1;
rep(i
,1,n
+1){
rep(j
,lim
,min(i
,x
)+1){
rep(k
,max((ll
)1,i
-m
+1),i
){
f
[i
][j
]=max(f
[i
][j
],f
[k
][j
-1]+a
[i
]);
}
}
if(i
%m
==0) lim
++;
}
ll ans
=0;
rep(i
,n
-m
+1,n
+1) ans
=max(ans
,f
[i
][x
]);
cout
<<ans
<<endl
;
}
}
int main(){
IOS
;
solve();
return 0;
}
