链接
http://poj.org/problem?id=2228
题意
在一天 $n$ 个小时中取 $b$ 个小时，使权值和最大，$b$ 个小时可分成若干段，每段的第一个小时的权值不计入总和，第 $n$ 个小时与第一个小时相连
思路
记 $f[i][j][0]$ 为前 $i$ 个小时中睡了 $j$ 个小时且第 $i$ 个小时不在睡，$f[i][j][1]$ 为前 $i$ 个小时中睡了 $j$ 个小时且第 $i$ 个小时在睡
转移方程：
$\begin{cases}
f[i][j][0]=\max(f[i-1][j][0],f[i-1][j][1]) \
f[i][j][1]=\max(f[i-1][j-1][0],f[i-1][j-1][1]+w[i])
\end{cases}$
因为首尾相连，所以第 $n$ 个小时会影响第一个小时
当第 $n$ 个小时没有睡：$f[1][0][0]=f[1][1][1]=0$，结果为 $f[n][b][0]$
当第 $n$ 个小时在睡：$f[1][0][0]=0,f[1][1][1]=w[1]$，结果为 $f[n][b][1]$
取最大值
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
const int N=4000;
int w[N];
int f[N][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,b;
cin>>n>>b;
for(int i=1;i<=n;i++) cin>>w[i];
memset(f,0xc0,sizeof f);
f[0][0]=f[1][1]=0;
for(int i=2;i<=n;i++)
for(int j=min(i,b);j>=0;j--) {
f[j][0]=max(f[j][0],f[j][1]);
if(j) f[j][1]=max(f[j-1][0],f[j-1][1]+w[i]);
}
int res=f[b][0];
memset(f,0xc0,sizeof f);
f[0][0]=0,f[1][1]=w[1];
for(int i=2;i<=n;i++)
for(int j=min(i,b);j>=0;j--) {
f[j][0]=max(f[j][0],f[j][1]);
if(j) f[j][1]=max(f[j-1][0],f[j-1][1]+w[i]);
}
res=max(res,f[b][1]);
cout<<res<<endl;
return 0;
}
|