[ABC285E] Work or Rest-环形背包
wflengxuenong
·
·
个人记录
题目大意；
某国一个礼拜有N 天。国王高桥准备把每一天安排为 节假日或者工作日。如果i号是工作日，那么动力是
拿到题目，感觉无从下手。\
先枚举，假设只有1天休息，就枚举是哪天休息。\
根据题意，只与距离前后休息的天数有关。与具体哪天休息无关。 \
$*。。。。。。* 16，25，43，34，52，61 ，$ 设一段工作日为$m$，那么$s=2*\sum a*\frac m 2
可以统计出$1...n$连续工作时间的效率值$s_i$。\
设每段背包状态为$。。。* $。
设定第一天为休息日。做完全背包 背包总体积为$n；1*（.。。*） （。。。*）$最后一个*和第一个*重合
有n-1个物品， 体积为1到n，价值为s0到sn-1
细节处理，要和开头环起来，
1：0
2：11 a1
3 12 21 2a1
4 13 22 31 2a1+a2
5 14 23 32 41 2a1+2a2
6 2a1+2a2+a3
7 2a1+2a2+2a3
- 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+9;
ll n,a[N],w[N],f[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++){//..* i包含结尾休息日
w[i]=w[i-1]+a[i/2];
}
memset(f,-32,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){//物品
for(int j=i;j<=n;j++){//背包体积
f[j]=max(f[j],f[j-i]+w[i]) ;
}
}
cout<<f[n]<<endl;
}
```