总计 $30$ 题。
洛谷
总计 $17$ 题。
P1002
没什么好说的，注意一下细节。
如果马的掌控范围不在棋盘内，特判防 RE。
$\Huge 不开 long\ long 见祖宗！！！$
#include<bits/stdc++.h>
using namespace std;
long long f[50][50];
int dx[]={1,1,-1,-1,2,-2,2,-2,0};
int dy[]={2,-2,2,-2,1,1,-1,-1,0};
int main()
{
int n,m,x,y;
cin>>n>>m>>x>>y;
x++;
y++;
n++;
m++;
f[1][1]=1;
for(int i=0;i<=8;i++)
{
int X=dx[i]+x,Y=dy[i]+y;
if(X>0&&Y>0)f[X][Y]=-1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1&&j==1)continue;
if(f[i][j]==-1)
{
f[i][j]=0;
continue;
}
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
cout<<f[n][m]<<endl;
return 0;
}P1044
对每个出栈的数，当前的方案数一定是比他小的方案数，乘上比它大的。
枚举一下即可。
#include<bits/stdc++.h>
using namespace std;
int f[20];
int main()
{
int n;
cin>>n;
f[0]=f[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
f[i]+=f[j-1]*f[i-j];
}
}
cout<<f[n]<<endl;
return 0;
}P1057
$f_{i,j}$ 表示第 $i$ 次传球，球在 $j$ 号同学的手中方案数。
每次往左往右加一下。
#include<bits/stdc++.h>
using namespace std;
int f[50][50];
int main()
{
int n,m;
cin>>n>>m;
f[0][1]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(j==1)f[i][n]+=f[i-1][j];
else f[i][j-1]+=f[i-1][j];
if(j==n)f[i][1]+=f[i-1][j];
else f[i][j+1]+=f[i-1][j];
}
}
cout<<f[m][1]<<endl;
return 0;
}[P1077]()
$f_{i,j}$ 表示 $n$ 种花选 $m$ 盆的最大值。
然后直接多重背包。
#include<bits/stdc++.h>
using namespace std;
int f[120][120];
int a[120];
const int mod=1e6+7;
int main()
{
int n,m;
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(a[i],j);k++)
{
f[i][j]+=f[i-1][j-k];
f[i][j]%=mod;
}
}
}
cout<<f[n][m]<<endl;
return 0;
}P1091
导弹拦截第一问做两遍，$n$ 规模较小 $\mathcal O(n^2)$ 的写法可过。
从左到右，从右到左各做一次，看能拦截多少“导弹”，最后减一下即为“拦截不住”即“该出列的学生”。
#include<bits/stdc++.h>
using namespace std;
int f[120];
int g[120];
int a[120];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j]<a[i])f[i]=max(f[i],f[j]);
}
f[i]++;
}
for(int i=n;i>=1;i--)
{
for(int j=i+1;j<=n;j++)
{
if(a[j]<a[i])g[i]=max(g[i],g[j]);
}
g[i]++;
}
int ans=-114514;
for(int i=1;i<=n;i++)
{
int x=f[i],y=g[i];
ans=max(x+y-1,ans);
}
cout<<n-ans<<endl;
return 0;
}P1095
$f_i$ 表示第 $i$ 个时刻最长距离。
我们先考虑只能位移，然后再扫一遍，如果走路更优就走路。
#include<bits/stdc++.h>
using namespace std;
int f[300020];
int main()
{
int m,s,t;
cin>>m>>s>>t;
for(int tt=1;tt<=t;tt++)
{
if(m>=10)
{
m-=10;
f[tt]=f[tt-1]+60;
}
else
{
m+=4;
f[tt]=f[tt-1];
}
}
for(int tt=1;tt<=t;tt++)
{
f[tt]=max(f[tt],f[tt-1]+17);
if(f[tt]>=s)
{
printf("Yes\n%d\n",tt);
return 0;
}
}
printf("No\n%d\n",f[t]);
return 0;
}P1358
热知识，杨辉三角可以用于求组合数。
$C^m_n$ 即为下标从 $0$ 开始的第 $n$ 行第 $m$ 列的数字。
#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int f[10020][120];
int main()
{
f[0][0]=1;
for(int i=1;i<=10000;i++)
{
f[i][0]=1;
}
for(int i=1;i<=10000;i++)
{
for(int j=1;j<=min(i,100);j++)
{
f[i][j]=f[i-1][j]+f[i-1][j-1];
f[i][j]%=mod;
}
}
int n,m;
long long ans=1;
cin>>n>>m;
while(m--)
{
int x;
cin>>x;
ans*=1LL*f[n][x];
ans%=mod;
n-=x;
}
cout<<ans<<endl;
return 0;
}P1439
乍一眼，是个 LCS。
但看了 阮行止 大佬的博客，受益匪浅，可以转换成 LIS 做。
所以这题是个复杂度只能为 $\mathcal O(n\log n)$ 的导弹拦截第一问。
但略有不同，导弹拦截是最长不上升子序列，即非严格 LDS，这题是最长上升，即 LIS。
但原理相同，二分优化。
#include<bits/stdc++.h>
using namespace std;
int a[100020];
int b[100020];
int f[100020];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]=i;
}
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
b[i]=a[x];
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(!ans||f[ans]<b[i])
{
f[++ans]=b[i];
}
else
{
int mid=lower_bound(f+1,f+ans+1,b[i])-f;
f[mid]=b[i];
}
}
cout<<ans<<endl;
return 0;
}P1616
完全背包板子。
$\Huge 不开 long\ long 见祖宗！！！$
#include<bits/stdc++.h>
using namespace std;
long long f[10000020];
int a[10020];
int b[10020];
int main()
{
int v,n;
cin>>v>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++)
{
for(int j=a[i];j<=v;j++)
{
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[v]<<endl;
return 0;
}P1679
完全背包。
价值为 $1$，重量为 $i^4$，问价值最小。
#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int f[100020];
int a[50];
int main()
{
memset(f,0x3f,sizeof(f));
int m;
cin>>m;
for(int i=1;i<=50;i++)
{
a[i]=i*i*i*i;
}
memset(f,0x7f,sizeof(f));
f[0]=0;
for(int i=1;i<=50;i++)
{
for(int j=a[i];j<=m;j++)
{
f[j]=min(f[j],f[j-a[i]]+1);
}
}
cout<<f[m]<<endl;
return 0;
}P1734
01背包，物品重量 $i$，价值 $a_i$。
$a_i$ 为 $i$ 的约数和去掉本身。
#include<bits/stdc++.h>
using namespace std;
int f[1020];
int a[1020];
int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(i%j==0)
{
a[i]+=j;
}
}
}
for(int i=2;i<=n;i++)
{
for(int j=n;j>=i;j--)
{
f[j]=max(f[j],f[j-i]+a[i]);
}
}
cout<<f[n]<<endl;
return 0;
}P1853
表面上题目挺吓人的，但其实只是完全背包，容量每年在变而已。
#include<bits/stdc++.h>
using namespace std;
long long f[10000020];
int a[10020];
int b[10020];
int main()
{
int v,n,x;
cin>>v>>x>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int k=1;k<=x;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=a[i];j<=v;j++)
{
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
v+=f[v];
}
cout<<v<<endl;
return 0;
}P2008
求最长不下降子序列时，顺便存一下和即可。
#include<bits/stdc++.h>
using namespace std;
int a[10020];
int f[10020];
int s[10020];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j]<=a[i])
{
if(f[j]>f[i])
{
f[i]=f[j];
s[i]=s[j];
}
}
}
s[i]+=a[i];
f[i]++;
cout<<s[i]<<" ";
}
return 0;
}P2347
和背包很类似，如果 $i$ 重量可以组成，$i+w_i$ 也可以组成。
暂且把 $w_i$ 看成题目中的砝码重量。
#include<bits/stdc++.h>
using namespace std;
bool f[1020];
int main()
{
f[0]=1;
for(int i=1;i<=6;i++)
{
int x,y=0;
scanf("%d",&x);
switch(i)
{
case 4:
y=5;
break;
case 5:
y=10;
break;
case 6:
y=20;
break;
default:
y=i;
}
for(int j=1;j<=x;j++)
{
for(int k=1000;k>=y;k--)
{
f[k]|=f[k-y];
}
}
}
int ans=0;
for(int i=1;i<=1000;i++)
{
ans+=f[i];
}
printf("Total=%d",ans);
return 0;
}当然，上个代码中，
for(int k=1000;k>=y;k--)
{
f[k]|=f[k-y];
}这一部分，可以简化。
C++ 一个 STL 容器，叫做 bitset。
bitset 自带或操作和位移操作。
那么，上述代码可以简化为
b|=b<<y;b<<y 是整个容器右移 $y$ 位，相当于原来代码 $-y$。
#include<bits/stdc++.h>
using namespace std;
bitset<1020>b;
int main()
{
b[0]=1;
for(int i=1;i<=6;i++)
{
int x,y=0;
scanf("%d",&x);
switch(i)
{
case 4:
y=5;
break;
case 5:
y=10;
break;
case 6:
y=20;
break;
default:
y=i;
}
for(int j=1;j<=x;j++)
{
b|=b<<y;
}
}
printf("Total=%d",b.count()-1);
return 0;
}P2639
01背包，装箱问题的双倍经验。
#include<bits/stdc++.h>
using namespace std;
int a[520];
int b[520];
int f[45020];
int main()
{
int v,n;
cin>>v>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=a[i];j--)
{
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[v]<<endl;
return 0;
}P2722
无限背包板子。
#include<bits/stdc++.h>
using namespace std;
int a[10020];
int b[10020];
int f[10020];
int main()
{
int v,n;
cin>>v>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++)
{
for(int j=b[i];j<=v;j++)
{
f[j]=max(f[j],f[j-b[i]]+a[i]);
}
}
cout<<f[v]<<endl;
return 0;
}P2925
01背包模板。
#include<bits/stdc++.h>
using namespace std;
int f[50020];
int a[5020];
int b[5020];
int main()
{
int v,n;
cin>>v>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=a[i];j--)
{
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
cout<<f[v]<<endl;
return 0;
}CF
总计 $6$ 题。
CF414B
又是个小清新题！
$f_{i,j}$ 表示最大 $i$，长度 $j$ 的序列个数。
伪代码如下：
枚举数列长度
枚举最大值
枚举与前一项的商但显然，复杂度 $\mathcal O(n^2k)$，然而本题 $n\leq 2000,k\leq 2000$ 明显不行。
考虑优化，如果前一项乘上商已经比 $n$ 大，就可以换一个最大值枚举了。
#include<bits/stdc++.h>
using namespace std;
int f[2020][2020];
const int mod=1e9+7;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
f[i][1]=1;
}
for(int j=2;j<=k;j++)
{
for(int i=1;i<=n;i++)
{
for(int _=1;_*i<=n;_++)
{
f[i*_][j]+=f[i][j-1];
f[i*_][j]%=mod;
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=f[i][k];
ans%=mod;
}
cout<<ans<<endl;
return 0;
}CF417A
无限背包。
题意很复杂，什么保送，什么赛制。
其实就是做无限背包后求 $\min\limits_{x \in [0,2]}\{f_{n\times m-x}\}$ 。
#include<bits/stdc++.h>
using namespace std;
int f[10020];
int a[10];
int b[10];
int main()
{
memset(f,0x3f,sizeof(f));
int c,d,n,m,k,v;
cin>>c>>d>>n>>m>>k;
if(n*m<=k)
{
cout<<0<<endl;
return 0;
}
v=n*m;
a[1]=n;
b[1]=c;
a[2]=1;
b[2]=d;
f[0]=0;
for(int kk=0;kk<=k;kk++)
{
v=n*m-kk;
for(int i=1;i<=2;i++)
{
for(int j=a[i];j<=v;j++)
{
f[j]=min(f[j],f[j-a[i]]+b[i]);
}
}
}
int ans=INT_MAX;
for(int kk=0;kk<=k;kk++)
{
v=n*m-kk;
ans=min(ans,f[v]);
}
cout<<ans<<endl;
return 0;
}CF431C
小清新题，爱了爱了。
用 $f_{i,0/1}$ 分别表示权值和为 $i$ 时，当前边权（看为 $j$）是否大于等于 $d$。
分成 $j\geq d$ 和 $j<d$ 两种情况。
-
$j\geq d$
$f_{i,0}= f_{i-j,0}$
$f_{i,1}=f_{i-j,0}+f_{i-j,1}$
-
$j<d$
$f_{i,0}= f_{i-j,0}$
$f_{i,1}=f_{i-j,1}$
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long f[120][2];
int main()
{
int n,k,d;
cin>>n>>k>>d;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
if(j>i)break;
if(j>=d)
{
f[i][1]+=f[i-j][0]+f[i-j][1];
f[i][1]%=mod;
}
else
{
f[i][0]+=f[i-j][0];
f[i][1]+=f[i-j][1];
f[i][0]%=mod;
f[i][1]%=mod;
}
}
}
cout<<f[n][1]<<endl;
return 0;
}CF545C
读完这题，你就会发现，这题是个贪心。
确实可以贪心，这题贪心十分简单，所以我们写 dp。
不为别的，就为装B。
dp 用 $f_{i,0/1/2}$ 表示第 $i$ 棵树不倒/往左边倒/往右边倒时的最大倒下树木。
-
$f_{i,0}$
即为前面的三种情况取最大值。
-
$f_{i,1}$
分类讨论，再空间足够时，讨论由哪种转变来。
-
$f_{i,2}$
如果可以就往右倒。
#include<bits/stdc++.h>
using namespace std;
int x[100020];
int h[100020];
int f[100020][3];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>h[i];
}
f[1][1]=1;
f[1][2]=x[2]-x[1]>h[1];
x[n+1]=2000000001;
for(int i=2;i<=n;i++)
{
f[i][0]=max(max(f[i-1][0],f[i-1][1]),f[i-1][2]);
if(h[i-1]+x[i-1]<x[i]-h[i])
{
f[i][1]=f[i-1][2]+1;
}
if(x[i-1]<x[i]-h[i])
{
f[i][1]=max(f[i][1],max(f[i-1][0]+1,f[i-1][1]+1));
}
if(x[i]+h[i]<x[i+1])
{
f[i][2]=max(max(f[i-1][0],f[i-1][1]),f[i-1][2])+1;
}
}
cout<<max(max(f[n][0],f[n][1]),f[n][2])<<endl;
return 0;
}CF933A
多看大佬博客受益匪浅。
所以这题暴力。
$n=2000$，暴力想都别想。
得到的最长不下降，一定是 $111\dots222\dots111\dots222$ 这种排列的。
我们用 $f_{i,j}$ 表示前 $i$ 个第 $j$ 段的答案。
那么可以得出：
$f_{i,1}=f_{i-1,1}+[a_i=1]$
