DP百题练（一）
目录
DP百题练（一）
鉴于本人 DP 太弱了，决定下定决心，连刷 100 题 DP。
题单见下：
日期什么的乱了也不要紧，这里只是初步的 DP学习场所，如果想进一步探究。。。
请看 DP百题练（二）
线性 DP
简简单单的线性 DP，DP的基础。
话说 USACO 的题目质量还真的很高呢。
贪心+DP。
能闪就闪肯定是最好的，跑步和闪分批处理就好了。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define N 300010
using namespace std;
int m,s,t,f[N];
int main(){
scanf("%d %d %d",&m,&s,&t);
for(int i=1;i<=t;i++){
if(m>=10){m-=10;f[i]=f[i-1]+60;}
else{m+=4;f[i]=f[i-1];}
}
for(int i=1;i<=t;i++){
f[i]=max(f[i],f[i-1]+17);
if(f[i]>=s){printf("Yes\n%d\n",i);return 0;}
}
printf("No\n%d\n",f[t]);
return 0;
}我绝对是颓废了，连这种等级的 DP 都想了半天
首先来一个逆向思维：删去 \(k\) 个数等于留下 \(n-k\) 个数，即题目变为选出 \(m(m=n-k)\) 个数留下。
接着来表示状态：首先进行到哪一本了肯定是要有的，接着已经选出了几本也是要的。
所以用 \(f[i][j]\) 表示从前 \(i\) 本书中选出了 \(j\) 本的最小值。
易得转移方程：
\(f[i][j]=min\{f[l][j-1]+abs(a[i].w-a[l].w)\}\)
其中 \(l=1…i-1\)，\(j=2…min(m,i)\)
再注意一下循环顺序，以及初始化。
显然 \(f[i][1]=0\) ，其余变为 \(INF\) 即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 110
using namespace std;
int n,k,m,f[N][N];
struct node{
int h,w;
}a[N];
bool cmp(node a,node b){
return a.h<b.h;
}
int main(){
scanf("%d %d",&n,&k);
m=n-k;
for(int i=1;i<=n;i++) scanf("%d %d",&a[i].h,&a[i].w);
sort(a+1,a+n+1,cmp);
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) f[i][1]=0;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
for(int l=2;l<=min(m,i);l++){
f[i][l]=min(f[i][l],f[j][l-1]+abs(a[i].w-a[j].w));
}
}
}
int ans=999999999;
for(int i=m;i<=n;i++) ans=min(ans,f[i][m]);
printf("%d\n",ans);
return 0;
}DP水题，转移方程随便推。
首先设 \(f[i][x][y][z]\) 表示已经解决了 \(i\) 个问题，三个人的位置分别为 \(x,y,z\),则有转移方程为：
\(f[i+1][p_{i+1}][y][z]=min(f[i+1][p_{i+1}][y][z]),f[i][x][y][z]+c[x][p_{i+1}]\)
\(f[i+1][x][p_{i+1}][z]=min(f[i+1][x][p_{i+1}][z]),f[i][x][y][z]+c[y][p_{i+1}]\)
\(f[i+1][x][y][p_{i+1}]=min(f[i+1][x][y][p_{i+1}]),f[i][x][y][z]+c[z][p_{i+1}]\)
但是显然时间上（\(O(LN^3)\)）和空间上都过不去，于是考虑缩小一维。
用 \(f[i][x][y]\) 表示已近解决了 \(i\) 个问题，其中一人的位置为 \(p_{i}\) ，另外两个的位置为 \(x,y\)。
\(f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[p_i][p_{i+1}])\)
\(f[i+1][p_i][y]=min(f[i+1][p_i][y],f[i][x][y]+c[x][p_{i+1}])\)
\(f[i+1][x][p_i]=min(f[i+1][x][p_i],f[i][x][y]+c[y][p_{i+1}])\)
按照题目要求，再判断 \(x!=y!=p_i\) 就好了，答案为 \(min_{x!=y!=p_n}\){\(f[n][x][y]\)}。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 1005
#define L 205
using namespace std;
int n,l,c[L][L],p[N],f[N][L][L];
int main(){
scanf("%d %d",&l,&n);
for(int i=1;i<=l;i++)
for(int j=1;j<=l;j++)
scanf("%d",&c[i][j]);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
memset(f,0x3f,sizeof(f));
f[0][1][2]=0;
p[0]=3;
for(int i=0;i<n;i++)
for(int x=1;x<=l;x++)
for(int y=1;y<=l;y++)
if(x!=p[i] && y!=p[i] && x!=y){
f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[p[i]][p[i+1]]);
f[i+1][p[i]][y]=min(f[i+1][p[i]][y],f[i][x][y]+c[x][p[i+1]]);
f[i+1][x][p[i]]=min(f[i+1][x][p[i]],f[i][x][y]+c[y][p[i+1]]);
}
int ans=0x3f3f3f3f;
for(int i=1;i<=l;i++){
for(int j=1;j<=l;j++){
if(i!=j && i!=p[n] && j!=p[n])ans=min(ans,f[n][i][j]);
}
}
printf("%d\n",ans);
return 0;
}传纸条。
首先明白来回传纸条等于一次传两张纸条。
然后完整一下题意：当两张纸条同时传到一个格子时，那个格子的值只加一次。
再然后设 \(f[x1][y1][x2][y2]\) 表示第一张纸条传到 \((x1,y1)\) ，第二张纸条传到 \((x2,y2)\)。则：
\(f[x1][y1][x2][y2]=min(f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2][y2-1],f[x1][y1-1][x2-1][y2-1])+a[x1][y1]+a[x2][y2]\)
时间是 \(O(N^2*M^2)\) 的，容易炸（这题数据很水，可能能过）
#include <iostream>
#define maxn 55
using namespace std;
int f[maxn][maxn][maxn][maxn],a[maxn][maxn];
int n,m;
int max_ele(int a,int b,int c,int d){
if (b>a)
a = b;
if (c>a)
a = c;
if (d>a)
a = d;
return a;
}
int main(){
cin >> n >> m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin >> a[i][j];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=n;k++)
for (int l=j+1;l<=m;l++) //这里避免了 j==l，即避免了重合的情况发生
f[i][j][k][l]=max_ele(f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1],f[i-1][j][k-1][l])+a[i][j]+a[k][l];
cout << f[n][m-1][n-1][m] << endl;
return 0;
}然后想优化，发现和上一题思路类似，用一维表示路径，然后可以找规律省下两维。
即 \(f[i][x1][x2]\) 表示：走了 \(i\) 步，两张纸条的横坐标分别是 \(x1,x2\)，易得 \(x1+y1=x2+y2=i+1\)。
**注意，没有走动时算 \(i=1\) **，则：
\(f[i][x1][x2]=max(f[i-1][x1-1][x2-1],f[i-1][x1-1][x2],f[i-1][x1][x2-1],f[i-1][x1][x2])+a[x1][y1]+a[x2][y2]\)
时间复杂度 \(O((N+M)*N^2)\)，有了很大的改善，同时要注意注意特判重合的情况。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define N 55
using namespace std;
int n,m,a[N][N],f[N*2][N][N];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=m+n-1;i++){
for(int x1=1;x1<=n;x1++){
for(int x2=1;x2<=n;x2++){
int y1=i+1-x1;
int y2=i+1-x2;
if(y1<1 || y2<1 || y1>m || y2>m) continue;
f[i][x1][x2]=max(max(f[i-1][x1-1][x2-1],f[i-1][x1-1][x2]),max(f[i-1][x1][x2-1],f[i-1][x1][x2]))+a[x1][y1]+a[x2][y2];
if(x1==x2){// 特判重合情况
f[i][x1][x2]-=a[x1][y1];
}
}
}
}
printf("%d\n",f[n+m-1][n][n]);
return 0;
}真 · 神题（码量不是一般的大）
考虑到一个凸多边形一定是连续的多行组成。可以考虑每行选哪几个格子。
设 0为单调伸长， 1为单调伸短。
设 \(f[i][j][l][r][x (0/1)][y (0/1)]\) 为第 i 行，已经选出j个格子，第i行选择了[l,r] 区间的最大值。左右端点x,y分别为单调伸长 / 单调伸短 的最大权值。
状态转移：
若 x=0,y=0，则 \(f[i][j][l][r][x][y]=max(f[i−1][j−(r−l+1)][l′][r′][0][0])+cost(i,l,r)\) ，其中\(l<=l′<=r′<=r,j>=r−l+1\)。
若 x=0,y=1，则 \(f[i][j][l][r][x][y]=max(f[i−1][j−(r−l+1)][l′][r′][0][0/1])+cost(i,l,r)\)，其中\(l<=l′<=r<=r′,j>=r−l+1\)。
若 x=1,y=0， 则 \(f[i][j][l][r][x][y]=max(f[i−1][j−(r−l+1)][l′][r′][0/1][0])+cost(i,l,r)\)，其中\(l′<=l<=r′<=r,j>=r−l+1\)。
若 x=1,y=1， 则 \(f[i][j][l][r][x][y]=max(f[i−1][j−(r−l+1)][l′][r′][0/1][0/1])+cost(i,l,r)\)，其中\(l′<=l<=r<=r′,j>=r−l+1\)。
初始状态：$ f[i][0][l][r][0][0]=0(0<=i<=n,1<=l<=r<=m)$，其余为负无穷。
目标：\(maxf[i][k][l][r][0/1][0/1](1<=i<=n)\)
输出方案只需通过状态转移延展即可。\(cost(i,l,r)\)用前缀和计算
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 16;
struct S{
int i, j, l, r, x, y;
}pre[N][N * N][N][N][2][2], t;
int n, m, k, a[N][N], f[N][N * N][N][N][2][2];
int ans = 0;
int inline cost(int i, int l, int r){
return a[i][r] - a[i][l - 1];
}
void print(S x){
if(x.j == 0) return;
print(pre[x.i][x.j][x.l][x.r][x.x][x.y]);
for(int i = x.l; i <= x.r; i++)
printf("%d %d\n", x.i, i);
}
int main(){
memset(f, 0xcf, sizeof f);
scanf("%d%d%d", &n, &m, &k);
for(int r = 0; r <= n; r++) {
for(int i = 1; i <= m; i++){
for(int j = i; j <= m; j++)
f[r][0][i][j][0][0] = 0;
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &a[i][j]), a[i][j] += a[i][j - 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
for(int l = 1; l <= m; l++){
for(int r = l; r <= m; r++){
if(j < r - l + 1) continue;
//x = 0, y = 0;
for(int l1 = l; l1 <= r; l1++){
for(int r1 = l1; r1 <= r; r1++){
int &v = f[i][j][l][r][0][0], val = f[i - 1][j - (r - l + 1)][l1][r1][0][0] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][0][0] = (S){i - 1, j - (r - l + 1), l1, r1, 0, 0};
}
}
}
//x = 0, y = 1;
for(int l1 = l; l1 <= r; l1++){
for(int r1 = r; r1 <= m; r1++){
for(int y1 = 0; y1 < 2; y1++) {
int &v = f[i][j][l][r][0][1], val = f[i - 1][j - (r - l + 1)][l1][r1][0][y1] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][0][1] = (S){i - 1, j - (r - l + 1), l1, r1, 0, y1};
}
}
}
}
// x = 1, y = 0;
for(int l1 = 1; l1 <= l; l1++){
for(int r1 = l; r1 <= r; r1++){
for(int x1 = 0; x1 < 2; x1++) {
int &v = f[i][j][l][r][1][0], val = f[i - 1][j - (r - l + 1)][l1][r1][x1][0] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][1][0] = (S){i - 1, j - (r - l + 1), l1, r1, x1, 0};
}
}
}
}
// x = 1, y = 1;
for(int l1 = 1; l1 <= l; l1++){
for(int r1 = r; r1 <= m; r1++){
for(int x1 = 0; x1 < 2; x1++) {
for(int y1 = 0; y1 < 2; y1++) {
int &v = f[i][j][l][r][1][1], val = f[i - 1][j - (r - l + 1)][l1][r1][x1][y1] + cost(i, l, r);
if(v < val) {
v = val, pre[i][j][l][r][1][1] = (S){i - 1, j - (r - l + 1), l1, r1, x1, y1};
}
}
}
}
}
if(j == k){
for(int x = 0; x < 2; x++) {
for(int y = 0; y < 2; y++) {
if(ans < f[i][j][l][r][x][y]) {
ans = f[i][j][l][r][x][y], t = (S){i, j, l, r, x, y};
}
}
}
}
}
}
}
}
printf("Oil : %d\n", ans);
print(t);
return 0;
}很简单的 DP ，但是好像也可以用最短路之类的东东求解（好像复杂了很多）
转移方程来一发：f[i]=min(f[i],f[j]+a[j][i]);。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 210
using namespace std;
int n,a[N][N],f[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(f,0x3f,sizeof(f));
f[1]=0;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
f[i]=min(f[i],f[j]+a[j][i]);
}
}
printf("%d\n",f[n]);
return 0;
}字符串与 DP 的完美结合，用 \(trie+dp\) 完美解决。 （其实可以用 \(set\) 但是我不会）
如果当前的字符串从后往前截了有一段集合中的串且截去这段串后的字串是合法的话那么当前串也是合法的。
类似于贪心，证明我不会，反正是对的。（不负责.jpg）
不会 \(trie\) 的话去学 \(set\) 吧。（字符串 \(Hash\) 也是可以的）
最后提一下 \(s.substr(a,b)\) 表示从字符串 \(s\) 中取出下标为 \(a-b\) 的子串。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#define N 200010
using namespace std;
int n,m,trie[N][30],tot=1;
bool sum[N],f[N];
string s,p;
void insert(string a){
int p=0;
for(int i=0;i<a.length();i++){
int ch=a[i]-'A';
if(!trie[p][ch]) trie[p][ch]=++tot;
p=trie[p][ch];
}
sum[p]=true;
return;
}
bool chck(string a){
int p=0;
for(int i=0;i<a.length();i++){
p=trie[p][a[i]-'A'];
if(!p) return false;
}
return sum[p];
}
int main(){
memset(sum,false,sizeof(sum));
memset(f,false,sizeof(f));
f[0]=true;
while(cin>>s){
if(s==".") break;
insert(s);
m=max(m,(int)s.size());
}
p=" ";
while(cin>>s){
p=p+s;
}
int ans=0;
for(int i=1;i<p.size();i++){
for(int j=min(m,i);j>=1;j--){
string tt=p.substr(i-j+1,j);
if(chck(tt) && f[i-j]){
ans=i;
f[i]=true;
break;
}
}
}
printf("%d\n",ans);
return 0;
}硬是把一道看上去像是 \(Manacher\) 的题目（仅标题）做成了 \(LCS\)。
看出来之后就没有难度了。
它可以这么理解，正序与倒序“公共”的部分就是我们回文的部分。
如果把正序与倒序公共的部分减去你就会惊奇的发现剩余的字符就是你所要添加的字符，也就是所求的正解。
例如样例数据：ab3bd
ad da把不回文的加起来就是我们梦寐以求的东西：回文串（卧槽？太没追求了）
把ad，da加起来成回文串就是adb3bda。
所以这个问题就可以转化成了求最长公共子序列的问题，将字符串的长度减去它本身的“回文的”字符便是正解。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 1010
using namespace std;
int f[N][N];
char s1[N],s2[N];
int main(){
scanf("%s",s1+1);
int n=strlen(s1+1);
for(int i=1;i<=n;i++){
s2[i]=s1[n-i+1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
printf("%d\n",n-f[n][n]);
return 0;
}好像挺简单的（除了记录路径）
用 \(f[i][j]\) 表示第 \(i\) 束花插到第 \(j\) 个花盆的最大价值。
易得状态转移方程：
\[f[i][j]=max_{i\leq j\leq m-n+i,1\leq k<j}\{f[i-1][k]\}+a[i][j]
\]
记得初始化 \(f[1][i]=a[1][i](1\leq i\leq m-n+1)\)。
然后终点讲一下记录路径：DP 中记录路径的方法一般为开一个与 \(f[]\) 等大的数组记录路径并递归输出。
然后就没有了 ヾ(◍°∇°◍)ﾉﾞ
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 110
using namespace std;
int n,m,a[N][N],f[N][N],pre[N][N],p[N];
void print(int x,int y){
if(x==1) {printf("%d ",y);return;}
print(x-1,pre[x][y]);
printf("%d ",y);
return;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=m-n+1;i++){
f[1][i]=a[1][i];
pre[1][i]=i;
}
for(int i=2;i<=n;i++)
for(int j=i;j<=m-n+i;j++)
for(int k=1;k<j;k++)
if(f[i-1][k]+a[i][j]>f[i][j]){
f[i][j]=f[i-1][k]+a[i][j];
pre[i][j]=k;
}
int ans=0,jl;
for(int i=n;i<=m;i++){
if(f[n][i]>ans){
ans=f[n][i];
jl=i;
}
}
printf("%d\n",ans);
int xa=n,xb=jl;
print(xa,xb);
return 0;
}把 DP 题做成了贪心+模拟题的蒟蒻。
一拿道题以为是什么玄学 DP，感觉很难的样子，但是当我看到数据范围我就改变了想法。
因为 \(n\leq 20000\)，所有 \(O(n^2)\) 的做法显然都不是正解，那么既然是 \(O(n)\) 的，就只能猜一猜了。
观察数据，我找到以下规律：每行都是从上一行的左/右端点走来的。
然后就变成模拟题了，当然模拟还是有些技巧的，这里就让读者自己思考了。
现在来讲讲这个做法的正确性：
由于不能往上走，无论在哪个端点，一定是从另一端点走来，而一端点距离上一行同侧端点最近。
然后就没了：（可以用滚动数组优化空间复杂度）
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 20010
using namespace std;
int n,f[N][2],l[N],r[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d %d",&l[i],&r[i]);
f[1][0]=r[1]-1+r[1]-l[1];
f[1][1]=r[1]-1;
for(int i=2;i<=n;i++){
f[i][0]=min(f[i-1][0]+abs(l[i-1]-r[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-r[i])+r[i]-l[i]+1);
f[i][1]=min(f[i-1][0]+abs(l[i-1]-l[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-l[i])+r[i]-l[i]+1);
}
printf("%d\n",min(f[n][0]+n-l[n],f[n][1]+n-r[n]));
return 0;
}当年第一次参加普及组的题目，现在回忆起来还真是有点意思。 （可惜这道题还是想了好久）
简化题意
我们不妨认为时间是一条数轴，每名同学按照到达时刻分别对应数轴上可能重合的点。安排车辆的工作，等同于将数轴分成若干个左开右闭段，每段的长度 \(\geq m\)。原本的等车时间之和，自然就转换成所有点到各自所属段右边界的距离之和。
基础 DP
设 \(f[i]\) 表示对数轴上 \((-\infty,\ i]\) 分段，且最后一段的右边界是 \(i\)，\((-\infty,\ i]\) 内的点到各自所属段右边界的距离之和最小值。转移式：
\[f_i=min_{j\leq i-m}\{f_i+\sum_{j<t_k\leq i}i-t_k\}
\]
设最后一段对应 \((j,\ i]\)，既然它的长度 \(\geqslant m\) ，则有 \(j \leqslant i - m\) 。我们知道 \(j < t_k \leqslant i\)，意味着第 \(k\) 个点在这段中，它到右端的距离 \(= i - t_k\)，因而产生这么多的贡献。累加贡献，与 \(j\) 以前的最优答案 \(f_j\)，即可推出转移式。
另外，特判 \((-\infty,\ i]\) 单独作为一段的边界情况，即 \(f_i = \sum\limits_{t_k \leqslant i}i - t_k\)。
然而我们对 \(\sum\limits_{j < t_k \leqslant i} i-t_k\) 束手无策，如何快速求出呢？这时前缀和有了重大用途。拆，拆，拆！
\[\sum_{j<t_k\leq i}i-t_k=(\sum_{j<t_k\leq i}i)-(\sum_{j<t_k\leq i}t_k)=(cnt_i−cnt_j)×i−(sum_i−sum_j)
\]
其中，\(cnt_i\) 表示 \((-\infty,\ i]\) 中点的个数，\(sum_i\) 表示 \((-\infty,\ i]\) 中点的位置之和。顺便改写下刚才的转移式：
\[f_i = \min_{j \leqslant i-m}\{ f_j + (cnt_i - cnt_j) \times i - (sum_i - sum_j)\}
\]
这里令 \(t = \max\limits_{1\leqslant i \leqslant n}\{t_i\}\)，最终答案只需在 \(\geqslant ti\) 找最小的 \(f_i\) 即可。实际上，\([t,\ t + m)\) 包含了所有可能的答案。
优化1：剪去无用转移
时间复杂度爆炸，怎么办？
实际上只需要：
\[f_i=min_{i-2m<j\leq i-m}\{f_j+(cnt_i-cnt_j)\times i-(sum_i-sum_j)\}
\]
不知你是否看到了区别？仍然考虑 \((j,\ i]\) 段的长度，由于分的段数不会增大答案，当它的长度 \(\geqslant 2m\) 时，我们完全可以再给它切一刀，得到不劣的答案。通过此性质，可剪去大量无用转移。
时间复杂度降至 \(O(tm)\)，按照写法常数可获得 \(70\) ~ \(100\) 不等的成绩，并不排除在 \(CCF\) 少爷机上超时的可能。
优化2：剪去无用状态
举个例子，假设正在求 \(f_i\)，但在 \((i-m,\ i]\) 中没有任何点，这个 \(f_i\) 相对来说就是 “无用” 的。原因是若最后一段长度恰好 \(= m\)，这里面又没有任何点，不分割也罢。长度 \(>m\) 时，完全可以把这一段的右边界往左“拖”，产生不劣的答案。
然而直接扔掉这个状态，会与上一个优化缩小转移范围起冲突，故无用的位置令 \(f_i = f_{i-m}\)，防止漏解。
可以证明“有用”的位置 \(\leqslant nm\) 个，故时间复杂度再次优化成 \(O(nm^2 + t)\)。期望得分 \(100\) 分。代码：
#include <cstdio>
#include <algorithm>
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, cnt[maxT], sum[maxT], f[maxT];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &ti); t = std::max(t, ti);
cnt[ti]++; sum[ti] += ti;
}
for (int i = 1; i < t + m; i++) { cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } // 前缀和.
for (int i = 0; i < t + m; i++) {
if (i >= m && cnt[i - m] == cnt[i]) { f[i] = f[i - m]; continue; } // 剪去无用状态.
f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
for (int j = std::max(i - m - m + 1, 0)/*剪去无用转移*/; j <= i - m; j++) { f[i] = std::min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j])); }
}
for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
printf("%d\n", ans);
return 0;
}如此优美的文章怎么可能是我写的
以上内容全部转载自这篇blog
这…算是最简单的数据结构优化 DP 吗
简单的 DP ，因为最高的地方不可能被别人刷新，所以用一个优先队列来维护，每次取出队首，满足无后效性。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int i,j,num,f;
};
struct cmp1{
bool operator()(node x,node y){
return x.num>y.num;
}
};
priority_queue<node,vector<node>,cmp1>q;
int n,m,maxn,maxj,maxi,w,top=0,g[101][101],f[101][101];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=1;
cin>>g[i][j];
node a;
a.i=i;a.j=j;a.f=0;a.num=g[i][j];
q.push(a);
}
}
while(!q.empty()){
node now1=q.top();
int i=now1.i;
int j=now1.j;
int now=now1.num;
q.pop();
if(g[i-1][j]<now) f[i][j]=max(f[i][j],f[i-1][j]+1);
if(g[i+1][j]<now) f[i][j]=max(f[i][j],f[i+1][j]+1);
if(g[i][j-1]<now) f[i][j]=max(f[i][j],f[i][j-1]+1);
if(g[i][j+1]<now) f[i][j]=max(f[i][j],f[i][j+1]+1);
if(maxn<f[i][j]) maxn=f[i][j];
}
cout<<maxn;
return 0;
}省选 DP 果然不同凡响。┐(‘～`；)┌
显然如果一行或一列有 \(>3\) 个炮就是不合法的，所以可以用三进制状压拿到 \(50pts\)。
但是我们的追求怎么能停留在 \(50\) 分呢？（你考 \(noip\) 时经常这样好吧）
所以就来康康正解吧。
设：\(f[i][j][k]\) 表示第 \(i\) 行有 \(j\) 个放了 \(1\) 个棋子的列，\(k\) 个放了 \(2\) 个棋子的列。
易得没放棋子的列\(=m-j-k\)。
确定情况
- 我们可以在当前第 \(i\) 行不放棋子。
- 我们可以在当前第 \(i\) 行放一个棋子。
- 我们可以在当前第 \(i\) 行放两个棋子。
接下来就需要分类讨论这些情况。
一、不放棋子
直接继承上面的状态。
\(f[i][j][k]=f[i-1][j][k]\)
二、放一个棋子
放在有一个棋子的列：\(f[i][j][k]+=f[i-1][j+1][k-1]\times (j+1)\)
放在没有棋子的列：\(f[i][j][k]+=f[i-1][j-1][k]\times (m-(j-1)-k)\)
解释一下：
放在有一个棋子的列：
我们在某一个有一个棋子列放置棋子,会使这一列变为有两个棋子。
即我们要得到 \(f[i][j][k]\) 需要在 \(j+1\) 个有一个棋子的列放置棋子,变为 \(j\) 个有一个棋子的列。
而我们又会得到一个新的有两个棋子的列.因此我们之前必须有 \(k-1\) 个有两个棋子的列。
而我们又可以在 \((j+1)\) 中的任何一列放置这一个棋子，因此我们要 \(\times (j+1)\)。
放在没有棋子的列：
在一个没有棋子的列放置棋子,我们会得到一个新的有一个棋子的列。
即我们要从\(j-1\)得到 \(j\)。
而这个时候,我们有两个棋子的列的数量不会变,所以从 \(k\) 传递即可。
又因为我们在空的列中寻找，所以要 \(\times(m-(j-1)-k)\)
三、放两个棋子
有一个棋子的列，没有棋子的列各放一个：\(f[i][j][k]+=f[i-1][j][k-1]\times j\times (m-j-k+1)\)
都放在没有棋子的列：\(f[i][j][k]+=f[i-1][j-2][k]\times C_{m-j-k+2}^2\)
都放在有一个棋子的列：\(f[i][j][k]+=f[i-1][j+2][k-2]\times C_{j+2}^2\)
再解释一下：
有一个棋子的列，没有棋子的列各放一个：
这个时候,我们放置之后 :
一个没有棋子的列会变成一个有一个棋子的列,而一个有一个棋子的列会变成一个有两个棋子的列。
此时我们发现,
有一个棋子的列的数量不会变,因此第二维依旧为 \(j\)，
又因为我们会新增一个有两个棋子的列,所以我们需要 \(k-1\) 转移过来。
根据乘法原理,需要\(\times j \times (m-j-(k-1))\)。
都放在没有棋子的列：
此时我们放置之后，
会增加两个新的有一个棋子的列。
因此我们需要从 \(j-2\) 转移过来。
而两个棋子的列的数量并不会改变,所以依旧为 \(k\)。
根据组合数学,需要 \(\times C_{m-(j-2)-k}^{2}\)
都放在有一个棋子的列：
我们放置在有一个棋子的列之后：
这两个有一个棋子的列都会变成有两个子的列。
即 \(j+2\) 变成 \(j\)，从 \(k-2\) 变成 \(k\)。
根据组合数学,需要 \(\times C_{j+2}^{2}\)。
分析完毕
我们需要接下来做的就是判断边界,一定要判断！
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MOD 9999973
#define N 110
using namespace std;
int n,m;
long long f[N][N][N];
int C(int x){
return ((x*(x-1))/2)%MOD;
}
int main(){
scanf("%d %d",&n,&m);
f[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m-j;k++){
f[i][j][k]=f[i-1][j][k];
if(k>=1) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
if(j>=1) f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1);
if(k>=1) f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1);
if(j>=2) f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2);
if(k>=2) f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2);
f[i][j][k]%=MOD;
}
}
}
long long ans=0;
for(int i=0;i<=m;i++){
for(int j=0;j<=m-i;j++){
ans=(ans+f[n][i][j])%MOD;
}
}
printf("%lld\n",(ans+MOD)%MOD);
}背包
DP中特殊而重要的一类。
分为0/1背包、完全背包、多重背包…
LG1077 摆花
早就想写题解了，貌似是第一次在机房考试时的题目 （当时我做了什么）
正解是 0/1 背包，赶时间的直接看方法三。
方法一：简单的动态规划
定义状态：\(f(i,j)\) 表示前 \(i\) 个数总和为 \(j\) 的方案数。
简简单单的状态转移方程：\(\sum^{a_i}_{k=0} f(i-1,f[j-k])\)。
时间复杂度：\(O(nm\times a_i)\)。
空间复杂度：\(O(nm)\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], f[maxn][maxn];
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
f[0][0] = 1;
for(int i=1; i<=n; i++)
for(int j=0; j<=m; j++)
for(int k=0; k<=min(j, a[i]); k++)
f[i][j] = (f[i][j] + f[i-1][j-k])%mod;
cout<<f[n][m]<<endl;
return 0;
}方法二：滚动数组优化
思想不变，状态不变，时间也不变…
空间复杂度：\(O(2m)\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], f[2][maxn], t;
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
f[0][0] = 1;
for(int i=1; i<=n; i++)
{
t = 1-t; //滚动
for(int j=0; j<=m; j++)
{
f[t][j] = 0; //注意初始化
for(int k=0; k<=min(j, a[i]); k++)
f[t][j] = (f[t][j] + f[1-t][j-k])%mod;
}
}
cout<<f[t][m]<<endl;
return 0;
}方法三：0/1 背包
通过观察上面的代码，二维数组，数组滚动优化空间……还有那熟悉的格式…
猛然发现这怎么可能不是背包呢（01背包）？
既然是背包，那么就可以为所欲为啦… [邪恶.jpg]
直接压成一维的01背包！！！
时间不变，空间复杂度：\(O(m)\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 110
using namespace std;
int n,m,a[N],f[N];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=1;k<=min(a[i],j);k++){
f[j]=(f[j]+f[j-k])%1000007;
}
}
}
printf("%d\n",f[m]);
return 0;
}CH5201 数字组合
入门题 （我刷这么多水题干什么），0/1背包。
这个我连方程都懒得推，好吧还是写一下：f[j]+=f[j-a[i]]。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,f[10010],a[1010];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j--){
f[j]+=f[j-a[i]];
}
}
printf("%d\n",f[m]);
return 0;
}LG1060 开心的金明
0/1 背包的水题啦，很简单的啦，转移方程略有不同。
\(f[j]=max(f[j],f[j-v[i]]+v[i]*p[i])\)
还是好简单，注意倒序循环就好了。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 30
#define M 30010
using namespace std;
int m,n;
int v[N],p[N],f[M];
int main(){
scanf("%d %d",&m,&n);
for(int i=1;i<=n;i++) scanf("%d %d",&v[i],&p[i]);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);
}
}
int ans=0;
for(int i=1;i<=m;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}LG1048 采药
感觉最近水题刷太多了…
就是裸的 0/1 背包，没啥好说的…
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define N 110
#define T 1010
using namespace std;
int t,n,f[T],v[N],w[N];
int main(){
scanf("%d %d",&t,&n);
for(int i=1;i<=n;i++) scanf("%d %d",&v[i],&w[i]);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
for(int j=t;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
int ans=0;
for(int i=0;i<=t;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}LG1507 NASA的食物计划
两维的 0/1 背包（别告诉我两维你就不会做了）
转移方程来一发：f[j][k]=max(f[j][k],f[j-v[i]][k-p[i]]+w[i]);。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#define N 55
using namespace std;
int V,P,n,v[N],p[N],w[N],f[410][410];
int main(){
scanf("%d %d %d",&V,&P,&n);
for(int i=1;i<=n;i++) scanf("%d %d %d",&v[i],&p[i],&w[i]);
for(int i=1;i<=n;i++){
for(int j=V;j>=v[i];j--){
for(int k=P;k>=p[i];k--){
f[j][k]=max(f[j][k],f[j-v[i]][k-p[i]]+w[i]);
}
}
}
printf("%d\n",f[V][P]);
return 0;
}LG1802 5倍经验日
分类讨论的 0/1 背包还真是第一次见到。
一般的 0/1 背包就是 \(m-v[i]\) ，这里却不一样了，不打药也是可以赢经验的。
易得转移方程：
\(f[j]=\bigg\{^{max(f[j]+lose[i],f[j-use[i]]+win[i])(use[i] \leq j)}_{f[j]+lose[i](use[i]>j)}\)
然后再加一句：十年OI一场空，没开 long long 见祖宗。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 1010
#define M 1010
using namespace std;
int n,m;
long long lose[N],win[N],use[N],f[M];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld %lld %lld",&lose[i],&win[i],&use[i]);
lose[i]*=5;
win[i]*=5;
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
for(int j=m;j>=use[i];j--){
f[j]=max(f[j]+lose[i],f[j-use[i]]+win[i]);
}
for(int j=use[i]-1;j>=0;j--){
f[j]+=lose[i];
}
}
printf("%lld\n",f[m]);
return 0;
}LG2340 Cow Exhibition G
原来背包还能这么玩 (」゜ロ゜)」
首先一只奶牛要么选要么不选，这符合 0/1 背包的模型。
但是物品的体积和价值怎么办呢？
这里就有一个新方法了：用其中一个当价值，另一个当体积。（是不是很神奇）
然后注意一下两点：
- 数组的下标不能为负数，所以要整体向右移动 \(400000\) 位（最大值）
- 当价值为负数时，应当使用正序循环。（与正数相反）
背包容量就是 \(800000\)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define N 410
#define M 800000+100
using namespace std;
int n,a[N],b[N],f[M];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
memset(f,0xcf,sizeof(f));
f[400000]=0;
for(int i=1;i<=n;i++){
if(a[i]>=0){
for(int j=800000;j>=a[i];j--){
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
else{
for(int j=0;j<=800000+a[i];j++){
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
}
int ans=0;
for(int i=400000;i<=800000;i++){
if(f[i]>0){
ans=max(ans,f[i]+i-400000);
}
}
printf("%d\n",ans);
return 0;
}CH5202 自然数拆分
完全背包的经典应用，主要是学到了一些语言上的东西。
很简单的转移方程：f[j]=(f[j]+f[j-i]) % 2147483648u。
但是后面的 \(u\) 就很玄学，原来是这样的：
当要定义一个无符号整型常亮时，可以采用数字+u的方法。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 4010
#define MOD 2147483648
using namespace std;
int n,f[N];
int main(){
scanf("%d",&n);
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
f[j]=(f[j]+f[j-i])%2147483648u;
}
}
printf("%d\n",f[n]>0?f[n]-1:2147483647);
return 0;
}LG1832 A+B Problem再升级
筛法+完全背包，数据范围很小，甚至可以打表（但是完全没有必要）
没什么好说的了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 1010
using namespace std;
int n,a[N],cnt=0;
bool p[N];
long long f[N];
void get_sushu(){
memset(p,false,sizeof(p));
for(int i=2;i<=n;i++){
if(p[i]) continue;
a[++cnt]=i;
for(int j=i*i;j<=n;j+=i)
p[j]=true;
}
return;
}
int main(){
scanf("%d",&n);
get_sushu();
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=cnt;i++){
for(int j=a[i];j<=n;j++){
f[j]+=f[j-a[i]];
}
}
printf("%lld\n",f[n]);
return 0;
}LG5662 纪念品
说实话真的是好题，要是让我今年打普及说不定就因为这道题 \(AK\) 不了。（自测的时候撑死没想到背包）
首先看部分分吧，关键是 \(T=2\) 的一部分。
很容易想到：
把 \(M\) 当做背包容量，把第一天的价值当做体积，把两天的差价当做 价值，这样来做一个完全背包。
然后进一步向后推广：
把 \(i-1\) 天的最大值当做背包容量，把 \(a[i][j]\) 当做体积，把 \(a[i+1][j]-a[i][j]\) 当做价值（即两天差价）
开开心心地做完全背包。
总结一下：
- 一道完全背包的题目。
- 特点是分阶段进行，每个阶段时都将 \(f[]\) 数组清零，同时每次结束时都更新 \(m\) 的值（即容量）。
方程写一下：
\(f[k]=max(f[k],f[k-a[i][j]]+a[i+1][j]-a[i][j])\)
\(m=max(m,f[m]+m)\)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 110
#define M 10010
using namespace std;
int t,n,m,f[M],a[N][N];
int main(){
scanf("%d %d %d",&t,&n,&m);
for(int i=1;i<=t;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=t;i++){
memset(f,0,sizeof(f));
for(int j=1;j<=n;j++)
for(int k=a[i][j];k<=m;k++)
f[k]=max(f[k],f[k-a[i][j]]+a[i+1][j]-a[i][j]);
m=max(m,f[m]+m);
}
printf("%d\n",m);
return 0;
}多重背包模板
有 \(N\) 种物品，其中第 \(i\) 种物品的体积为 \(V_i\) ，价值为 \(W_i\) ，而且有 \(C_i\) 个。
有一个容积为 \(M\) 的背包，要求选若干个物品放入背包，使得物品总体积不超过 \(M\) 的情况下总价值最大。
直接拆分法
直接把物品 \(i\) 当做独立的 \(C_i\) 个物品，然后就变成了共有 \(\sum_{i=1}^N C_i\) 个物品的 \(0/1\) 背包求解。
时间复杂度：\(O(M*\sum_{i=1}^N C_i)\) 。（简单说就是 \(T\) 到飞起）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 1010
#define M 100010
using namespace std;
int n,m,w[N],v[N],c[N],f[M];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d %d %d",&v[i],&w[i],&c[i]);
}
memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=c[i];j++){
for(int k=m;k>=v[i];k--){
f[k]=max(f[k],f[k-v[i]]+w[i]);
}
}
}
int ans=0;
for(int i=0;i<=m;i++){
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}二进制拆分法
刚刚我们是直接拆分，现在用一个高级一些的方法：二进制拆分。
以用数字的二进制形式来解释
比如：
- \(7 = 111\) 它可以分解成 \(001\) \(010\) \(100\) 这三个数可以组合成任意小于等于7 的数。
- \(15 = 1111\) 可分解成 \(0001\) \(0010\) \(0100\) \(1000\) 四个数字。
- \(13 = 1101\) 则分解为 \(0001\) \(0010\) \(0100\) \(0110\) 前三个数字可以组合成，7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。
简单的说：
将 \(C_i\) 分解为：\(2^0,2^1,2^2,…,2^{p}，C_i-2^{p+1}+1\)，即可表示所有数。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 1010
#define M 100010
using namespace std;
int n,m,c,v,w;
int f[M];
int cnt = 0; //分解后可得到多少种物品
int value[N]; //用来保存分解后的物品价值
int size[N]; //用来保存分解后物品体积
void pre_work(){
while(n--){
scanf("%d %d %d",&c,&w,&v);
for(int k=1;k<=c;k<<=1){
value[++cnt]=k*w;
size[cnt]=k*v;
c-=k;
}
if(c>0){
value[++cnt]=c*w;
size[cnt]=c*v;
}
}
return;
}
int main(){
scanf("%d %d",&n,&m);
pre_work();
//现在用count 代替 n 就和01 背包问题完全一样了
memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=cnt;i++){
for(int j=m;j>=size[i];j--){
f[j]=max(f[j],f[j-size[i]]+value[i]);
}
}
int ans=0;
for(int i=0;i<=m;i++){
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}POJ1742 Coins
楼教主的题目，好像是很玄学的题目（随机数据，第一次交没过，第二次就过了…）
貌似是各种卡常（连单调队列都有的没过，我这个二进制拆分竟然过了…）
二进制拆分上面就说了，这里不再做过多的介绍，简简单单就过了。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 110
#define M 100010
using namespace std;
int n,m,cnt=0;
int a[N],c[N],value[10010];
bool f[M];
void pre_work(){
for(int i=1;i<=n;i++){
for(int j=1;j<=c[i];j<<=1){
value[++cnt]=a[i]*j;
c[i]-=j;
}
if(c[i]>0){
value[++cnt]=c[i]*a[i];
}
}
return;
}
int main(){
while(~scanf("%d %d",&n,&m) && n){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
cnt=0;
pre_work();//核心部分
for(int i=1;i<=m;i++) f[i]=false;
f[0]=true;
for(int i=1;i<=cnt;i++){
for(int j=m;j>=value[i];j--){
f[j]|=f[j-value[i]];
}
}
int ans=0;
for(int i=1;i<=m;i++) if(f[i]) ans++;
printf("%d\n",ans);
}
return 0;
}LG1833 樱花
简简单单的多重背包，但是有一些要注意的。
二进制拆分就水过了，注意一下时间的处理和 \(P_i=0\) 时的情况。
- 时间的处理：首先这是一个背包 （没看出来就别做了），容积是两时间之差：
m=(h2-h1)*60+(m2-m1)。 - \(P_i=0\) 时的情况：即可以看无限次（变成了完全背包），有以下操作：
if(c==0) c=m/v+1;。
这个自己理解吧 （想一想为什么）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 100010
#define M 100010
using namespace std;
int n,m,v,w,c,cnt=0;
int f[M],value[N],size[N];
char a;
void init(){
int h1,h2,m1,m2;
scanf("%d",&h1);
a=getchar();
scanf("%d %d",&m1,&h2);
a=getchar();
scanf("%d %d",&m2,&n);
m=(h2-h1)*60+(m2-m1);
return;
}
void pre_work(){
for(int i=1;i<=n;i++){
scanf("%d %d %d",&v,&w,&c);
if(c==0) c=m/v+1;
for(int j=1;j<=c;j<<=1){
value[++cnt]=w*j;
size[cnt]=v*j;
c-=j;
}
if(c){
value[++cnt]=c*w;
size[cnt]=c*v;
}
}
return;
}
int main(){
init();
pre_work();
memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=cnt;i++){
for(int j=m;j>=size[i];j--){
f[j]=max(f[j],f[j-size[i]]+value[i]);
}
}
int ans=0;
for(int i=0;i<=m;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}P1776 宝物筛选
感觉多重背包的题目真的是一个比一个裸。
简简单单的做法就过了，就是二进制拆分搞定。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define N 100010
#define M 40010
using namespace std;
int n,m,f[M],cnt=0;
int v,w,c,value[N],size[N];
void pre_work(){
for(int i=1;i<=n;i++){
scanf("%d %d %d",&v,&w,&c);
for(int j=1;j<=c;j<<=1){
value[++cnt]=v*j;
size[cnt]=w*j;
c-=j;
}
if(c){
value[++cnt]=v*c;
size[cnt]=w*c;
}
}
return;
}
int main(){
scanf("%d %d",&n,&m);
pre_work();
memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=cnt;i++){
for(int j=m;j>=size[i];j--){
f[j]=max(f[j],f[j-size[i]]+value[i]);
}
}
int ans=0;
for(int i=0;i<=m;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}分组背包模板
分组背包问题是这样的：
给定 \(N\) 组物品，其中第 \(i\) 组有 \(C_i\) 个物品，其中第 \(j\) 个物品的价值为 \(W_{ij}\) ，体积为 \(V_{ij}\) 。
给你一个容积为 \(M\) 的背包，求在每组中至多挑选一组的情况下，能得到的最大价值。
很容易想到二维的 DP 方法：
\(F[i,j]=max\bigg\{_{max_{1\leq k \leq C_i}\{F[i-1,j-V_{ik}]+W_{ik}\}}^{F[i-1,j]}\)
分别对应选或不选的方法。
和其他背包类似，可以通过倒叙循环省掉一维空间。
memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=1;k<=c[i];j++)//k在最里层
if(j>=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);一定要注意循环顺序
手机扫一扫
移动阅读更方便
你可能感兴趣的文章