数字三角形模型
AcWing 898. 数字三角形
/*
动态规划：状态的表示与计算
状态表示：
f(i,j)表示所有从起点走到(i,j)的路径中，数字和最大的路径
(某种集合的某种属性)
状态计算(集合划分)：
f(i,j)可分为从左上角走到(i,j)或者从右上角走到(i,j)
f(i,j)=max( f(i-1,j-1)+a[i][j] , f(i-1,j)+a[i][j] )
*/
#include<iostream>
using namespace std;
const int N=510,INF=1e9;
int n;
int a[N][N];
int f[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){//读入数字三角形，下标从1开始
for(int j=1;j<=i;j++) cin>>a[i][j];
}
// 因为数据中可能有负数，为了防止从边界外转移过来（全局变量默认为0），
// 所以要将边界外赋值为-INF
for(int i=0;i<=n;i++){
//为了在计算状态时不处理边界，将所有状态初始化为负无穷
for(int j=0;j<=i+1;j++) f[i][j]=-INF;
}
f[1][1]=a[1][1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++) f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
}
int res=-INF;
for(int i=1;i<=n;i++) res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}
//倒序dp，不需要考虑边界问题
#include<iostream>
using namespace std;
const int N=510;
int f[N][N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>f[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=i;j>=1;j--){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
}//全局变量默认初始化为0，所以最底层数据计算没有问题
}
cout<<f[1][1]<<endl;
}
AcWing 1015. 摘花生
/*
从集合角度考虑DP
状态表示：
某种集合的某种属性(属性一般为max，min，数量)
f(i,j)表示所有从(1,1)走到(i,j)的路线中摘到花生的最大值，最后所求恰好是f(n,m)
状态计算：
对应于集合划分，划分时注意不重不漏，不漏一定要满足，但是当所求属性为最值时划分集合是否重复不重要
很重要的划分依据：“最后”
本题根据最后一步(i,j)从哪儿来划分：从上面下来；从左边过来。两类取最大值
f(i,j) = max( f(i,j-1) , f(i-1,j) ) + w(i,j)
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int w[N][N];
int f[N][N];
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){//状态计算时需要用到上一行，上一列的信息，下标从1开始便于处理边界情况
for(int j=1;j<=m;j++){
cin>>w[i][j];
}
}
//计算状态，线性顺序
//注意是否需要初始化，这道题计算状态时，行列下标都从1开始，那对于那些下标为0的行列来说
//如果未特意初始化，全局变量默认为0，一定要多考虑边界行列状态计算时是否会有影响
//这道题中因为是求最值，并且都为非负整数，所以不初始化没有影响
//会说这么多是希望注意，很多题在这一步时是不初始化是会有影响的
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
}
}
cout<<f[n][m]<<endl;
}
return 0;
}
//空间压缩
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m;
int w[N][N];
int f[N];
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[j]=max(f[j],f[j-1])+w[i][j];
}
}
cout<<f[m]<<endl;
//空间压缩，由于多组数据，注意置0
memset(f, 0, sizeof f);
}
return 0;
}
AcWing 1018. 最低通行费
/*
动态规划的表示：一般网格图f(i,j),线形图f(i),背包问题第一维是物品，第二维是体积。需要经验
与上一题摘花生相似，但上道题要求走时只能往下或右走，这道题呢?
由于题目中的时间限制，等价于走时不能往回走，也就是只能往下或右走
所以两道题非常相似，只是一个求最大值，一个求最小值
也因此，两者对边界问题的处理不同
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, INF = 1e9;
int n;
int w[N][N];
int f[N][N];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin>>w[i][j];
/*
这里与上一题不同，上一道题因为求的是最大值，且均为非负整数，所以下标为0的行列不初始化，
默认为0没有任何问题，但这里求的是最小值，均为非负整数，所以如果下标为0的行列不初始化，
全局变量默认为0,则状态计算时所有状态全部为0那么如何初始化呢？由于求的是最小值，
所以下标为0的行列全部初始化为正无穷即可
*/
for (int i = 0; i <= n; i ++ ) {
f[i][0] = f[0][i] = INF;
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
/*
这里边界问题中对于f(1,1)要特别注意，上道题求最大值时，上左均为0，取最大值加自身权重后没有
任何问题,这里对均为正无穷的上左求最小值加自身权重任为正无穷，所以要单独把f(1,1)拿出来特判
*/
if (i == 1 && j == 1) f[i][j] = w[i][j];
else {
f[i][j] = min(f[i - 1][j] + w[i][j], f[i][j - 1] + w[i][j]);
}
}
cout<<f[n][n];
return 0;
}
/*
空间压缩
*/
#include<iostream>
using namespace std;
const int N=110,INF=1e9;
int w[N][N],f[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cin>>w[i][j];
}
for(int i=0;i<=n;i++) f[i]=INF;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1) f[j]=w[i][j];
else{
f[j]=w[i][j]+min(f[j],f[j-1]);
}
}
}
cout<<f[n]<<endl;
}
AcWing 1027. 方格取数
/*
状态表示：
上两道题都是走一次，这道题需要走两次，如何扩展到走两次呢？
走一次：f(i,j)表示所有从(1,1)走到(i,j)的路径的最大值
走两次：
可以两条路线同时走，可能会走过相同的格子，但对于这些格子的数只能计算一次
f(i1,j1,i2,j2)表示所有从(1,1)分别走到(i1,j1),(i2,j2)的路径的最大值
因为是同时走，所以第一条路线走k步到达(i1,j1),第二条路线同样走k步到达(i2,j2)，因此
i1+j1=i2+j2=k
所以可以降维到三维
f(i1,j1,i2,j2)变为f(k,i1,i2)，其中j1=k-i1,j2=k-i2
状态计算：
对于每条路线，各自都可以向下或向右走到(i1,j1),(i2,j2)，所以两两组合，有四种情况可以划分集合
以及要特别注意，计算每个状态时，如果当前两条路线走到了相同的点，那么这个点的数只计算一次
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=15;
int n;
int w[N][N];
int f[2*N][N][N];
int main(){
cin>>n;
int a,b,c;
while(cin>>a>>b>>c,a||b||c) w[a][b]=c;//输入到a,b,c均为0时停止，所以是||
for(int k=2;k<=n+n;k++){
for(int i1=1;i1<k;i1++){
for(int i2=1;i2<k;i2++){
int t=w[i1][k-i1];
if(i1!=i2) t+=w[i2][k-i2];//判断是否走到同一格子，因为同时走，必然同时到
int& x=f[k][i1][i2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
}
}
}
cout<<f[n+n][n][n]<<endl;
return 0;
}
AcWing 275. 传纸条
/*
这道题与方格取数问题只有一点不同，那就是在方格取数中，同一个格子可以重复走，只是格子的数只能被计算一次，而这道题是不能走相同的格子
但是这道题完全能够用方格取数的代码解决是因为不管在那道题中，最优解永远不会由两条相交的路径组成，两条路径相交时，一定能绕路找到更优的解
*/
#include <iostream>
using namespace std;
const int N = 55;
int n, m;
int w[N][N];
int f[N * 2][N][N];
int main()
{
cin>>n>>m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin>>w[i][j];
for(int k=2;k<=n+m;k++){
for(int i1=1;i1<k;i1++){
for(int i2=1;i2<k;i2++){
int t=w[i1][k-i1];
if(i1!=i2) t+=w[i2][k-i2];
int& x=f[k][i1][i2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
}
}
}
cout<<f[n + m][n][n];//注意这里都是n因为是i1，i2的范围
return 0;
}
最长上升子序列模型
AcWing 895. 最长上升子序列
/*
DP
状态表示：
f[i]表示所有以第i个数结尾的上升子序列中长度最大的上升子序列的长度
满足某种条件的某种集合的某种属性
状态计算：
集合划分，这道题f[i]中第i个数一定存在于上升子序列中，
所以根据它的前一个数去分类，前一个数可能没有，可能是数组中第一个元素，
可能是数组中第二个元素，一直到可能是数组第i-1个元素
f[i]=max(f[j]+1) j=0,1,2...i-1;
f[0]到f[i-1]不一定都能取，因为可能有某个数大于f[i]
时间复杂度：O(n^2)
*/
#include<iostream>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;//只要a[i]一个数
for(int j=1;j<i;j++){
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
res=max(res,f[i]);
}
cout<<res<<endl;
return 0;
}
//记录转移过程
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N],g[N];//g[N]存储转移过程
vector<int> res;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
f[i]=1;//只要a[i]一个数
g[i]=0;//表示第i个数没有从谁转移过来
for(int j=1;j<i;j++){
if(a[j]<a[i]) {
if(f[i]<f[j]+1){
f[i]=f[j]+1;//记录f[i]是从谁转移过来的
g[i]=j;
}
}
}
}
int k=0;//存储最大值的下标
for(int i=1;i<=n;i++){
if(f[k]<f[i]) k=i;
}
cout<<f[k]<<endl;
while(f[k]){
res.push_back(a[k]);
k=g[k];
}
for(int i=res.size()-1;i>=0;i--) cout<<res[i]<<' ';
return 0;
}
AcWing 896. 最长上升子序列 II
/*
与上道题一样，只是数据范围变大，上道题n^2做法会超时
考虑优化
依次遍历数组每个元素，将前面求得的最长上升子序列按长度分类
存储各个长度的上升子序列结尾的最小值，相同长度的上升子序列中，结尾更大的肯定
没有结尾较小的好，因为如果一个数可以接到较大的后面，也一定可以接到较小的后面
所以较大的没必要存下来，它是可被替换的，较小的适用范围更广
可证明各个长度的上升子序列结尾的最小值单调递增
当前遍历元素可以接到某一个上升子序列后面
换句话说，在不考虑边界情况的前提下，当前遍历元素可以替换这个递增的结尾序列中
第一个大于它的元素，也就是更新某个序列的结尾，
更新的意思是当前遍历的这个元素更适合当结尾
时间复杂度：对于每个元素二分查找 O(nlogn)
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ) cin>>a[i];
//通用做法：两种二分查找都可以做，考虑边界情况
q[0]=a[0];
//len表示数组q中最后一个元素的下标，因为从0开始，所有输出为len+1
int len = 0;
for (int i = 1; i < n; i ++ ){
// 先插入第一个元素，从第二个元素开始遍历
// 在结尾递增序列中找第一个大于等于当前遍历的元素，边界情况是最大元素都比它小
if(q[len]<a[i]){//边界情况
q[++len]=a[i];
}
else{
int l = 0, r = len;
while (l < r)
{
int mid = (l + r) >> 1;
if (q[mid] >= a[i]) r= mid;
else l = mid + 1;
}
q[l] = a[i];
}
}
cout<<len+1<<endl;
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ) cin>>a[i];
//通用做法：两种二分查找都可以做，考虑边界情况
q[0]=a[0];
//len表示数组q中最后一个元素的下标，因为从0开始，所有输出为len+1
int len = 0;
for (int i = 1; i < n; i ++ ){
// 先插入第一个元素，从第二个元素开始遍历
//在结尾递增序列中找最后一个小于当前遍历的元素，边界情况是最小元素都比它大
if(q[0]>=a[i]) q[0]=a[i];
else{
int l = 0, r = len;
while (l < r)
{
int mid = l + r +1>> 1;
if (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len=max(len,l+1);
q[l+1] = a[i];
}
}
cout<<len+1<<endl;
return 0;
}
#include <iostream>
using namespace std;
const int N = 100010;
int n,a[N],q[N];//存不同长度上升子序列的结尾最小值
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ) cin>>a[i];
int len = 0;//len表示数组q中有多少个不同长度的序列最小值
for (int i = 0; i < n; i ++ )
{//遍历，二分查找数组q中有多少个不同长度的序列最小值小于当前遍历元素的元素
int l = 0, r = len;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
cout<<len<<endl;
return 0;
}
AcWing 1017. 怪盗基德的滑翔翼
/*
确定滑行方向后就转化为了LIS问题,原问题相当于正向和反向以ai为结尾的最长上升子序列长度，
分别正向和反向各进行一次LIS，取得最大值即可。
*/
#include<iostream>
// #include<algorithm>
// #include<cstring>
using namespace std;
const int N=110;
int n;
int a[N],f[N];
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int res=0;
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++){
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
}
res=max(res,f[i]);
}
// memset(f,0,sizeof f);
for(int i=n-1;i>=0;i--){
f[i]=1;
for(int j=n-1;j>i;j--){
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
}
res=max(res,f[i]);
}
cout<<res<<endl;
}
return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int n;
int a[N],f[N];
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int len=0;
for(int i=0;i<n;i++){
int l=0,r=len;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
f[l+1]=a[i];
len=max(len,l+1);
}
memset(f,0,sizeof f);
int len_2=0;
for(int i=n-1;i>=0;i--){
int l=0,r=len_2;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
f[l+1]=a[i];
len_2=max(len_2,l+1);
}
memset(f,0,sizeof f);
int res=(len_2>len)?len_2:len;
cout<<res<<endl;
}
return 0;
}
AcWing 1014. 登山
/*
求先严格上升再严格下降的最长子序列的长度，根据哪个点为峰值去分类
先正序求以每个点a[i]为结尾的最长上升子序列的长度，再逆序求以同一点a[i]为结尾的最长上升子序列的长度
两者相加减1取最大值(因为a[i]取了两次)，上道题是两个序列整体求最大值
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N], g[N];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>a[i];
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i >= 1; i -- )
{
g[i] = 1;
for (int j = n; j > i; j -- )
if (a[i] > a[j])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
cout<<res;
return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int n;
int a[N],f[N],q[N],p[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int len=0;
for(int i=0;i<n;i++){
int l=0,r=len;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
f[l+1]=a[i];
len=max(len,l+1);
q[i]=l+1;
}
memset(f,0,sizeof f);
len=0;
for(int i=n-1;i>=0;i--){
int l=0,r=len;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
f[l+1]=a[i];
len=max(len,l+1);
p[i]=l+1;
}
int res=0;
for(int i=0;i<n;i++) res=max(res,q[i]+p[i]-1);
cout<<res<<endl;
return 0;
}
AcWing 482. 合唱队形
/*
上一道登山的题的对偶，最少去掉多少人，就是最多剩下多少人，也就是求先上升再下降的最长子序列的长度，改一下数据范围和输出就行
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N];
int f[N], g[N];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>a[i];
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i >= 1; i -- )
{
g[i] = 1;
for (int j = n; j > i; j -- )
if (a[i] > a[j])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
cout<<n-res;
return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int n;
int a[N],f[N],q[N],p[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int len=0;
for(int i=0;i<n;i++){
int l=0,r=len;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
f[l+1]=a[i];
len=max(len,l+1);
q[i]=l+1;
}
memset(f,0,sizeof f);
len=0;
for(int i=n-1;i>=0;i--){
int l=0,r=len;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
f[l+1]=a[i];
len=max(len,l+1);
p[i]=l+1;
}
int res=0;
for(int i=0;i<n;i++) res=max(res,q[i]+p[i]-1);
cout<<n-res<<endl;
return 0;
}
AcWing 1012. 友好城市
/*
问题可理解为给定n条边，找尽可能多的互不相交的边的数量
可以这样理解：只要某一岸的城市坐标越来越大，各自对应的另外一岸的城市坐标也越来越大，两两连接的桥必然互不相交，反证法可证明
也就是先对某一边的端点排序，再求排序之后的另外一边端点的最长上升子序列长度即可
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5010;
typedef pair<int,int> PII;
int n;
PII a[N];
int f[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
sort(a,a+n);
int res=0;
for(int i=0;i<n;i++){
f[i]=1;
for(int j=0;j<i;j++){
if(a[i].second>a[j].second) f[i]=max(f[i],f[j]+1);
}
res=max(res,f[i]);
}
cout<<res;
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5010;
typedef pair<int, int> PII;
int n;
PII a[N];
int f[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
sort(a,a+n);
int len=0;
for(int i=0;i<n;i++){
int l=0,r=len;
while(l<r){
int mid=(l+r+1)>>1;
if(f[mid]<a[i].second) l=mid;
else r=mid-1;
}
f[l+1]=a[i].second;
len=max(len,l+1);
}
cout<<len<<endl;
return 0;
}
AcWing 1016. 最大上升子序列和
/*
与最长上升子序列问题相比，一个求长度，一个求和的最大值
状态表示：f(i)表示所有以a[i]结尾的上升子序列中和最大的序列的和
状态计算：f[i]=max(f[i],f[j]+a[i])原来是长度加1，现在是和加a[i]
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=n;i++){
f[i]=a[i];//原来是只有a[i]一个数时长度至少为1，现在是和至少为a[i]
for(int j=1;j<i;j++){
if(a[i]>a[j]) f[i]=max(f[i],f[j]+a[i]);
}
res=max(res,f[i]);
}
cout<<res<<endl;
return 0;
}
AcWing 1010. 拦截导弹
/*
第一问就是求最长不上升子序列的长度，只需把判断条件由f(j)<f(i)改成f(j)>=f(i)即可
第二问这样思考，遍历数组每个元素，遍历到当前元素a[i]时，要么把这个元素放入新创建序列中，要么把这个元素放入某个已有子序列结尾
所以用一个数组q来存储之前所有不上升子序列的结尾元素
如果a[i]大于数组中每一个数，则新建一个不上升子序列，也就是把这个元素放入数组q
否则，找到q中大于等于a[i]的最小的数，将其替换
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int h[N], f[N], q[N];
int main()
{
while (cin>>h[n]) n ++ ;
int res = 0, cnt = 0;
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (h[i] <= h[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
int k = 0;//cnt表示当前有多少个序列，k表示最后一个序列的下标
while (k < cnt && q[k] < h[i]) k ++ ;
q[k] = h[i];
if(k >= cnt) cnt ++;
}
cout<<res<<endl<<cnt;
return 0;
}
#include<iostream>
using namespace std;
const int N=1010;
int h[N],f[N],q[N];
//f[N]存储不同长度的不上升子序列的最小结尾值 有一个元素的序列最小结尾值是f[1]
//q[N]存储不同种系统能拦截的结尾最小值 q[1]就是第一个系统能拦截的结尾最小值
int n;
int main(){
while(cin>>h[n]) n++;
int len = 0,cnt=0;//len就是表示此时序列最多有多少个元素
for (int i = 0; i < n; i ++ )
{
int l = 0, r = len;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (f[mid] >= h[i]) l = mid;//找到最后一个大于等于的元素，替换后面的元素
else r = mid - 1;
}
len = max(len, r + 1);
f[r + 1] = h[i];//f[0]没有意义，始终未被赋值
l = 0, r = cnt;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (q[mid] < h[i]) l = mid;//找到最后一个小于的元素
else r = mid - 1;
}
cnt = max(cnt, r + 1);
q[r + 1] = h[i];
}
cout<<len<<endl<<cnt;
return 0;
}
AcWing 187. 导弹防御系统
/*
上一道题，拦截导弹的高度只能不再上升，这道题可以选择拦截导弹的高度单调上升或者单调下降
这道题是最少能用多少个单调上升子序列和单调下降子序列把整个序列覆盖掉，而上一道题是最少能用多少个不再上升子序列把整个序列覆盖掉
遍历每枚导弹，对于当前遍历元素，与上道题相比，需要先多考虑这个元素是放在上升子序列中还是下降子序列中，这个确定之后就和上道题一样了
dfs暴力搜索，用全局变量记录最小值
不用bfs求解是因为空间会爆炸
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int h[N];
int up[N], down[N];//存储每个上升或下降子序列的结尾
/*
up数组表示所有严格上升子序列的结尾，它本身随下标是非严格单调下降的；
down数组表示所有严格下降子序列的结尾，它本身随下标是非严格单调上升的；
*/
int ans;
void dfs(int u, int su, int sd)
{//当前遍历到下标为u的元素，此时数组up和down中各自存储了su和sd个上升或下降子序列的结尾元素，也就是上升子序列和下降子序列各有多少个
if (su + sd >= ans) return;//直接return是因为在此之后已经不可能再把答案变小了
if (u == n)
{//前面n个元素已经遍历完了
ans = min(ans, su + sd);
return;
}
int k = 0;
//情况1 将当前元素放入上升子序列中
while (k < su && up[k] >= h[u]) k ++ ;
int t = up[k];
up[k] = h[u];
if (k < su) dfs(u + 1, su, sd);
else dfs(u + 1, su + 1, sd);
up[k] = t;
//情况2 将当前元素放入下降子序列中
k = 0;
while (k < sd && down[k] <= h[u]) k ++ ;
t = down[k];
down[k] = h[u];
if (k < sd) dfs(u + 1, su, sd);
else dfs(u + 1, su, sd+1);
down[k] = t;
}
int main()
{
while (cin >> n, n)
{
for (int i = 0; i < n; i ++ ) cin >> h[i];
ans = n;
dfs(0, 0, 0);
cout << ans << endl;
}
return 0;
}
AcWing 897. 最长公共子序列
/*
状态表示：
f(i,j)表示所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现
的子序列(公共子序列)中最长子序列的长度(max)
状态计算：
集合划分最主要的是不漏，如果属性是求最值，划分是否重复不重要，如果求数量，
不能重复
f(i,j)划分成四个部分
包含i和j f(i-1,j-1)+1(这种情况要考虑到需要a[i]和b[j]相等)
只包含i f(i,j-1)一定不包含j，可能包含i，可能不包含i
只包含j f(i-1,j)一定不包含i，可能包含j，可能不包含j
均不包含 f(i-1,j-1)
最后一种情况f(i-1,j-1)被f(i-1,j)或f(i,j-1)包含，所以不用单独考虑
中间两种情况的状态表示互有重复，且与只包含i(j)的情况不完全等价，而是包含关系
但因为是求最值，所以不遗漏才最重要
综上所述：
f(i,j)=max( f(i-1,j) , f(i,j-1) , f(i-1,j-1)+1)
*/
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];//注意定义时候别出错，y总这里最开始写成int，很久都没找到错误
int f[N][N];
int main()
{
cin>>n>>m>>a+1>>b+1;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout<<f[n][m]<<endl;
return 0;
}
AcWing 272. 最长公共上升子序列
/*
状态表示：
f(i,j)表示所有考虑A中前i个字母，B中前j个字母，并以b(j)结尾的公共上升子序列中最长公共上升子序列的长度
状态计算(对应集合划分)：
根据公共子序列是否包含a[i]分为两类
不包含：f[i-1][j]
包含：此时必然a[i]==b[j]，此时根据倒数第二个字母是谁再去集合划分
没有：1
b[1]:f[i-1][1]+1
...
b[j-1]:f[i-1][j-1]+1
*/
//直接实现，三重循环
#include <iostream>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>a[i];
for (int i = 1; i <= n; i ++ ) cin>>b[i];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];
if (a[i] == b[j])
{
int maxv = 1;
//求前缀最大值，所以用一个变量单独维护前缀就行，不需要单独循环求解
for (int k = 1; k < j; k ++ )
if (b[j] > b[k])
maxv = max(maxv, f[i - 1][k] + 1);
f[i][j] = max(f[i][j], maxv);
}
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
cout<<res;
return 0;
}
#include <iostream>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>a[i];
for (int i = 1; i <= n; i ++ ) cin>>b[i];
for (int i = 1; i <= n; i ++ )
{
// for (int j = 1; j <= n; j ++ )
// {
// f[i][j] = f[i - 1][j];
// if (a[i] == b[j])
// {
// int maxv = 1;
// for (int k = 1; k < j; k ++ )
// if (b[j] > b[k])
// maxv = max(maxv, f[i - 1][k] + 1);
// f[i][j] = max(f[i][j], maxv);
// }
// }
int maxv = 1;
for (int j = 1; j <= n; j ++ )
{//代码等价优化，避免最里层的重复运算
f[i][j] = f[i - 1][j];
//此时的maxv对应于1到j-1中满足条件a[i] > b[j]的f[i-1][...]+1的最大值
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
//如果有必要的话更新maxv,为下一次计算j+1准备
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
cout<<res;
return 0;
}
线性DP
AcWing 902. 最短编辑距离
/*
状态表示：
f(i,j)表示所有A中前i个字母转变成B中前j个字母的操作数的最小值
状态计算：
集合划分 三种情况
A中第i个字母增加一个元素后转变成功：f(i,j-1)
A中第i个字母删除后转变成功：f(i-1,j)
A中第i个字母修改后转变成功：f(i-1,j-1)+0/1(取决于a[i]=b[j]是否相等)
*/
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(){
cin>>n>>a+1>>m>>b+1;
//边界情况的确定，一些DP问题f[0][0]等于0就行，一些要单独考虑
//注意这里从0开始，一直到等于n(m)结束
for(int i=0;i<=n;i++) f[i][0]=i;
for(int i=0;i<=m;i++) f[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
}
}
cout<<f[n][m]<<endl;
return 0;
}
AcWing 899. 编辑距离
#include<iostream>
#include<string.h>
using namespace std;
const int N=15,M=1010;
int n,m;
char str[M][N];
int f[N][N];
int edit_dist(char a[],char b[]){
int n=strlen(a+1),m=strlen(b+1);//+1是抛开第0个空字符，从下标1开始计数
for(int i=0;i<=n;i++) f[i][0]=i;
for(int i=0;i<=m;i++) f[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
}
}
return f[n][m];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>str[i]+1;
while(m--){
char s[N];
int limt;
cin>>s+1>>limt;
int res=0;
for(int i=0;i<n;i++){
if(edit_dist(str[i],s)<=limt) res++;
}
cout<<res<<endl;
}
return 0;
}
背包问题
AcWing 2. 01背包问题
/*
动态规划问题一般从两个角度考虑，分别是状态表示与状态计算
状态表示：用几维表示状态，每一个状态(集合)的含义是什么
f(i,j)表示的是满足某些条件的集合的某种属性
DP优化都是对代码方程的等价变形
状态表示一般从两个角度考虑，分别是集合与属性
背包问题中集合是指所有选法的集合，这些选法满足两个条件
1.只考虑前i个物品 2.选出来的物品的总体积不超过j
属性一般有三种：最大值，最小值，数量 背包问题中是集合中选法的价值最大值
所以f(i,j)是指只考虑前i个物品，所有物品总体积不超过j的选法中价值的最大值
状态计算：集合的划分 如何把当前集合不重不漏的划分成若干个更小的子集
(不漏一定要满足，不重看情况)
背包问题：
for 物品
for 体积
for 决策
f(i,j)=max( f(i-1,j) , f(i-1,j-vi)+wi )
二维
f(i,j)是指只考虑前i个物品，所有物品总体积不超过j的选法中价值的最大值
f(i,j)分为两大类，分别是是否包含第i件物品
不包含：f(i-1,j)
包含：f(i-1,j-vi)+wi
f(i,j)=max( f(i-1,j) , f(i-1,j-vi)+wi )
*/
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
//下标从1开始是因为状态计算时需要用到i-1
//初始化时枚举所有状态，也就是f[0~n][0~m]，对于f[0][0~m]来说，必然为0
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//对f(i,j)=max( f(i-1,j) , f(i-1,j-vi)+wi )来说，左边一定存在，右边不一定存在
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
//优化成一维，对代码做等价变形
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
//优化：二维变成一维 能够优化是因为f[i]这一层计算只用到的f[i-1]上面这一层
//f[j]用到的j和j-v[i]都小于等于j，所以可以改成一维数组来计算
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
//由于j-v[i]严格小于j，所以内层循环如果从小到大遍历，所以先去更新j-v[i]，然后才是j
//所以这样之后再计算f[j]时所用到的j-v[i]其实是第i层的，而不是i-1层的j-v[i]
//因此优化时，内层循环的遍历改为从大到小
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
//一维优化之后，下标从0开始也很方便
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>v[i]>>w[i];
for(int i=0;i<n;i++){//这儿取0是因为输入的时候也是从0开始
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
AcWing 423. 采药
/*
经典01背包问题
采药总时间相当于背包容量，每一株药相当于一件物品，采药时间相当于该物品的体积，
草药的价值相当于物品价值。
*/
#include <iostream>
using namespace std;
const int N = 1010;
int m, n;
int f[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
AcWing 1024. 装箱问题
/*
01背包问题裸题
没有价值，只有体积，把价值看成体积就行，使总体积最大
以及注意输出是剩余空间
*/
#include<iostream>
using namespace std;
const int N=20010;
int n,m;
int f[N];
int main(){
cin>>m>>n;
for(int i=0;i<n;i++){
int v;
cin>>v;
for(int j=m;j>=v;j--){
f[j]=max(f[j],f[j-v]+v);
}
}
// cout<<f[m]<<endl;刚开始输出没注意
cout<<m-f[m]<<endl;
return 0;
}
AcWing 1022. 宠物小精灵之收服
/*
二维费用的01背包问题
花费1：可用于收复精灵的精灵球数量(all)
花费2：可用于收复精灵的皮卡丘体力值(all-1：因为皮卡丘体力不能为0，所以能拿出来的体力是all-1)
价值：小精灵数量
状态表示：
f[i,j,k]表示所有考虑前i个物品，且花费1不超过j，花费2不超过k的选法的最大价值
状态计算：
根据是否选择第i个物品分类
f[i,j,k]=max( f[i-1,j,k] , f[i-1,j-v1[i],k-v2[i]]+1 )
*/
#include <iostream>
using namespace std;
const int N = 1010, M = 510;
int n, V1, V2;
int f[N][M];
int main()
{
cin >> V1 >> V2 >> n;
for (int i = 0; i < n; i ++ )
{
int v1, v2;
cin >> v1 >> v2;
for (int j = V1; j >= v1; j -- )
for (int k = V2 - 1; k >= v2; k -- )
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
cout << f[V1][V2 - 1] << ' ';
int k = V2 - 1;//k初始时是可用于收复精灵的皮卡丘体力最大值
//如果k可以变小的话，就尝试变小看行不行，如果变小之后收服数量不变的话就变小
while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k -- ;
//跳出循环时，k表示在收服最多小精灵的情况下，皮卡丘消耗的体力最小值
cout << V2 - k << endl;//注意输出，题目问的是剩余体力
return 0;
}
AcWing 8. 二维费用的背包问题
/*
状态表示：
f[i,j,k]表示所有只从前i个物品中选择，并且总体积不超过j，总重量不超过k的选法集合的最大值
状态计算：
f[i,j,k]=max( f[i-1,j,k] , f[i-1,j-v1[i],k-v2[i]]+w[i] )
*/
#include <iostream>
using namespace std;
const int N = 110;
int n, V, M;
int f[N][N];
int main()
{
cin >> n >> V >> M;
for (int i = 0; i < n; i ++ )
{
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; j -- )
for (int k = M; k >= m; k -- )
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
cout << f[V][M] << endl;
return 0;
}
AcWing 1020. 潜水员
/*
之前的二维费用问题f[i,j,k]表示所有从前i个物品中选择，并且总体积至多是j，总重量至多是k的选法集合的最大值
而这道题中f[i,j,k]表示所有从前i个物品中选,且氧气含量至少是j,氮气含量至少是k的所有选法的气缸重量总和的最小值
状态计算：
所有不包含物品i的所有选法：f[i - 1,j,k]
所有包含物品i的所有选法：f[i - 1,j - v1,k - v2]
注意：如果j - v1为负数也是可行的，与0等价。这是因为它代表当前所需氧气至少为j，而第i种物品所能提供的氧气超过j
满足条件，这个物品是可用的，用了之后，不再需要氧气，因此j - v1这一项置为0即可
扩展：
体积至多是j：初始化时价值f[0][j]=0(不管j为多少，都包含f[0][0]这一种方案，价值为0)，j-vi>=0
体积恰好为j: 初始化时价值f[0][0]=0，j为其他值都不合法，设为正负无穷取决于题目求最大还是最小值，j-vi>=0
体积至少为j：初始化时价值f[0][0]=0，j为其他值都不合法，设为正负无穷取决于题目求最大还是最小值，j-vi为负数也合理
*/
#include <cstring>
#include <iostream>
using namespace std;
const int N = 22, M = 80;
int n, m, K;
int f[N][M];
int main()
{
cin >> n >> m >> K;
//之前的f[i,j,k]当i==0时，因为是不超过j k 因此f[0,j,k]==0
//但这里因为是至少为j,k 所以当i==0时，只有f[0,0,0]==0,其他情况下的f[0,j,k]都是不合法的
//因为本题是求最小值，所以初始化为正无穷
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
while (K -- )
{
int v1, v2, w;
cin >> v1 >> v2 >> w;
for (int i = n; i >= 0; i -- )
for (int j = m; j >= 0; j -- )
f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
}
cout << f[n][m] << endl;
return 0;
}
AcWing 278. 数字组合
/*
可以转化为01背包问题求方案数
将总和M看作背包容量
将每个数Ai看作体积为Ai的物品
求总体积恰好是M，也就是恰好装满背包的方案数
状态表示：
f[i,j]是指所有只从前i个物品中选，且总体积恰好是j的方案的集合的数量
状态计算：
不包括i：f[i-1,j]
包括i：f[i-1,j-Ai]
f[i,j]=f[i-1,j]+f[i-1,j-Ai]
*/
//二维
#include <iostream>
using namespace std;
const int N = 110,M=10010;
int n, m;
int f[N][M];
int main()
{
cin >> n >> m;
for (int i = 0; i <= n; i ++ ) f[i][0]=1;
/*
注意方案数的初始化，如果有任意多个数，背包体积为0，一件物品都不选也是一种合理的方案
所以初始化时，对于任意的f[i][0]都为1
但是如果一件物品都没有，要去装满任意体积大于0的背包，找不出合理的方案，所以对于任意的
f[0][i](i>0)，初始化为0，而又因为f数组为全局变量，默认初始化为0，所以不用刻意初始化
只需初始化f[i][0]=1即可
*/
for (int i = 1; i <= n; i ++ )
{
int v;
cin >> v;
for (int j=1; j<=m; j++){
f[i][j] = f[i-1][j];
if(j >= v) f[i][j] += f[i-1][j-v];
}
}
cout << f[n][m] << endl;
return 0;
}
//一维
#include<iostream>
using namespace std;
const int N=110,M=1010;
int n,m;
int f[M];
int main(){
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++){
int v;
cin>>v;
for(int j=m;j>=v;j--){
f[j]+=f[j-v];
}
}
cout<<f[m]<<endl;
return 0;
}
AcWing 426. 开心的金明
/*
将原问题做如下转化:
总钱数相当于背包总容量；
每件物品的价格相当于体积；
每件物品的价格乘以重要度相当于价值；
01背包问题
*/
#include <iostream>
using namespace std;
const int N = 30010;
int n, m;
int f[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
w *= v;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
AcWing 11. 背包问题求方案数
/*
之前的一些题问的是装满背包的方案，这道题是使总价值最大的方案数
本题求01背包的最佳方案数，那么定义两个数组：f[N],cnt[N]
f[i]用为背包容积不超过i时最佳方案的总价值，
cnt[i]为背包容积不超过i时总价值最佳的方案数
*/
#include<iostream>
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;
int f[N], g[N];
int main()
{
int n, m;
cin>>n>>m;
for(int i = 0; i <= m; i ++) g[i] = 1;//什么也不装也是一种方案
//这里与y总只是g[]初始化不同，这是因为定义不同
for(int i = 1; i <= n; i ++)
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- )
{
int left = f[j], right = f[j - v] + w;
f[j] = max(left, right);
if (left > right) g[j] = g[j];
else if (left < right) g[j] = g[j - v];
else g[j] = g[j] + g[j - v];
g[j] %= mod;
}
}
cout<<g[m];
return 0;
}
AcWing 12. 背包问题求具体方案
/*
题目要求输出字典序最小的解，假设存在一个包含第1个物品的最优解，为了确保字典序最小
那么我们必然要选第一个。那么问题就转化成从2～N这些物品中找到最优解。之前的f(i,j)
记录的都是前i个物品总容量为j的最优解，那么我们现在将f(i,j)定义为从第i个元素到最后
一个元素总容量为j的最优解。接下来考虑状态转移：
f(i,j)定义为从第i个元素到最后一个元素总容量不超过j的最优解
状态计算：
f(i,j)=max(f(i+1,j),f(i+1,j−v[i])+w[i]) 计算时物品遍历从后往前
每个元素有三种状态
必选：f(1,m)=f(2,m−v[1])+w[1]
必不选：f(1,m)=f(2,m)
可选可不选：f(1,m)=f(2,m)=f(2,m−v[1])+w[1]，此时因为要字典序最小，选
在判断当前元素是否要选的时候需要用到后面的状态，所以状态这样表示，计算时从后往前
*/
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = n; i >= 1; i -- )
for (int j = 0; j <= m; j ++ )
{
f[i][j] = f[i + 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
int j = m;//表示还背包还剩多少空间
for (int i = 1; i <= n; i ++ )
//如果当前物品能够放进背包，并且在此基础上能够得到最优解
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
{
cout << i << ' ';
j -= v[i];
}
return 0;
}
AcWing 734. 能量石
/*
01背包问题，与之前普通01背包问题不同的是每一个物品的选择是有序的，所以先找到顺序
假设最优解的能量石排列长度为k(1<=k<=n)因为去掉了那些没有贡献的宝石，位置为：a1,a2,a3…ak
那么对于任意两个位置i=al,j=al+1(1<=l<k)
交换后两个宝石的贡献总和会变得更小，即（假设之前的总时间为t）：
Ei−t∗Li+Ej−(t+Si)∗Lj>Ej−t∗Lj+Ei−(t+Sj)∗Li
整理后：
Si∗Lj<Sj∗Li
这样，我们只要以如上条件作为宝石间排序的条件，进行一次sort
然后就是普通01背包问题
状态定义f[i][j]表示从排好序的前i个能量石中取，经过了恰好 j 时刻的最优解
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 10010;
int n;
struct Stone
{
int s, e, l;
bool operator < (const Stone& b)const{
return s*b.l<b.s*l;//注意这里要用乘法，因为用除法这里l可能为0
}
}stones[N];
int f[M];
int main()
{
int T;
cin >> T;
for (int C = 1; C <= T; C ++ )
{
cin >> n;
int m = 0;
for (int i = 1; i <= n; i ++ )
{
int s, e, l;
cin >> s >> e >> l;
stones[i] = {s, e, l};
m += s;
}
sort(stones + 1, stones + 1 + n);
memset(f,0,sizeof f);//每组数据状态计算之前注意初始化，避免之前组数据影响
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= stones[i].s; j-- )
{//当前在时刻j，也就是从j-s时刻开始吃的
int s = stones[i].s, e = stones[i].e, l = stones[i].l;
f[j] = max(f[j], f[j - s] + max(0, e - l * (j - s)));
}
int res = 0;
for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
printf("Case #%d: %d\n", C, res);
}
return 0;
}
AcWing 3. 完全背包问题
/*
对于01背包问题，可以按照第i种物品选0个或1个分类，类似，完全背包问题可按照第i种物品
选0,1,2...k个分类
(注意：虽然每种物品有无限个可选，但背包容量有限，所以最多选k个，其中k的限制条件
是k * v[i] <= 每个状态考虑的背包容量j)
所以状态转移方程 f(i,j)=max(f( i-1 , j- k * v[i] ) + k * w[i]) k>=0&&k*v[i]<=j
*/
//朴素做法 会超时 三维
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
//下标从1开始是因为状态计算时需要用到i-1
//枚举所有状态
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//k的限制条件是此时的考虑情况的背包容量
for(int k=0;k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
/*
状态转移方程 二维
f(i,j) =max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],...,f(i-1,j-k*v[i])+k*w[i])
f(i,j-v)=max( f(i-1,j-v[i]) ,f(i-1,j-2*v[i])+ w[i],...,f(i-1,j-k*v[i])+(k-1*w[i])
f(i,j)=max( f(i-1,j) , f(i, j-vi)+wi ) 完全背包问题优化方程
f(i,j)=max( f(i-1,j) , f(i-1,j-vi)+wi ) 01背包问题方程
*/
//二维优化做法
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
//一维优化做法
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){//注意这里与01背包问题的区别
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
AcWing 1023. 买书
/*
状态表示：
f[i,j]是指所有只从前i个物品中选，且总体积恰好是j的方案的集合的数量
状态计算：
根据第i个物品选多少个来划分
f(i,j)+=f( i-1 , j- k * v[i] ) k>=0&&k*v[i]<=j
优化：
f(i,j)=f(i-1,j)+f(i,j-v)
*/
//二维
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int v[5] = {0,10, 20, 50, 100};
int f[5][N];
int main()
{
cin >> n;
for (int i = 0; i <= 4; i ++ ) f[i][0]=1;
for (int i = 1; i <= 4; i ++ )
for (int j = 1; j <= n; j ++ ){
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]+=f[i][j-v[i]];
}
cout << f[4][n] << endl;//定义是f[5]表示下标从0到4，有五个下标
return 0;
}
//一维优化
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int v[5] = {0,10, 20, 50, 100};//int v[4] = {10, 20, 50, 100};
int f[N];
int main()
{
cin >> n;
f[0] = 1;//不管考虑前多少个物品，总体积恰好是0的方案只有一种，但如果题中是价值的话，这一种方案的价值是0
for (int i = 1; i <= 4; i ++ )//for (int i = 0; i < 4; i ++ )
for (int j = v[i]; j <= n; j ++ )
f[j] += f[j - v[i]];
cout << f[n] << endl;
return 0;
}
AcWing 1021. 货币系统
/*
与买书题类似
n种物品(每种物品无限个)，容量为m的背包，完全背包问题求方案数
状态表示：
f[i,j]是指所有只从前i个物品中选，且总体积恰好是j的方案的集合的数量
状态计算：
根据第i个物品选多少个来划分
f(i,j)+=f( i-1 , j- k * v[i] ) k>=0&&k*v[i]<=j
优化：
f(i,j)=f(i-1,j)+f(i,j-v)
*/
#include <iostream>
using namespace std;
typedef long long LL;
const int M = 3010;
int n, m;
LL f[M];//方案数较大，ll存储
int main()
{
cin >> n >> m;
f[0] = 1;//对应求方案数而言，最开始一个物品都不选也是一种方案
for (int i = 0; i < n; i ++ )
{
int v;
cin >> v;
for (int j = v; j <= m; j ++ )
f[j] += f[j - v];
}
cout << f[m] << endl;
return 0;
}
AcWing 532. 货币系统
/*
货币系统能简化是当其中一张货币面额可以被该系统下其他货币表示时，此货币对该系统能表示的面额没有影响
换言之这个货币没有存在的必要，所以将这类的货币从系统中去除就可以得到等价的更小数量货币系统。
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25010, M=110;
int n;
int a[M];
bool f[N];
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n);
//先排序，从小到大考虑每个数，依次判断当前数能否由前面的数表示出来，ai能否被前面的数表示可看作
//容量为ai的背包能否由体积为a1,a2...的物品恰好装满，完全背包问题
//也就是判断装满ai的方案数是否为0
int m = a[n - 1];
f[0] = 1;
int k = 0;//这里注意局部变量初始化时一定赋初值，不然输出尽可能出错
for (int i = 0; i < n; i ++ )
{
if (!f[a[i]]) k ++ ;//如果当前ai不存在一种拼凑方案，则要被选出来
for (int j = a[i]; j <= m; j ++ )
f[j] += f[j - a[i]];
}
cout << k << endl;
memset(f, 0, sizeof f);//多组测试数据，每组计算前清空之前组的计算
}
return 0;
}
AcWing 4. 多重背包问题
/*
与完全背包问题类似，多重背包问题可按照第i种物品选0,1,2…k个分类
(注意：虽然每种物品最多有s[i]个可选，再加上背包容量有限，所以最多选k个，
其中k的限制条件是k * v[i] <= 每个状态考虑的背包容量j&&k<=s[i])
所以状态转移方程 f(i,j)=max(f( i-1 , j- k * v[i] ) + k * w[i])
*/
//朴素做法 三维
#include<iostream>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//k的限制条件是此时的考虑情况的背包容量
for(int k=0;k*v[i]<=j&&k<=s[i];k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
//空间优化
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int j=m;j>=0;j--){
for(int k=0;k*v<=j&&k<=s;k++){
f[j]=max(f[j],f[j-k*v]+k*w);
}
}
}
cout<<f[m]<<endl;
return 0;
}
AcWing 5. 多重背包问题 II(二进制优化)
/*
先尝试完全背包问题优化思路f(i,j)，从转移方程入手
完全：背包最多放k个v 最后始终是-k*wi 求所有前缀最大值
f(i,j) =max(f(i-1,j),f(i-1,j-v[i])+w[i],...f(i-1,j-k*v[i])+k*w[i])
f(i,j-v)=max( f(i-1,j-v[i]) ,...f(i-1,j-k*v[i])+(k-1)*w[i])
f(i,j-2v)=max( f(i-1,j-2v[i]) ,... f(i-1,j-k*v[i])+(k-2)*w[i])
多重：第i类物品有s个 最后始终是+s*wi 求滑动窗口最大值
f(i,j) =max(f(i-1,j),f(i-1,j-v[i])+w[i],...f(i-1,j-s*v[i])+s*w[i] )
f(i,j-v)=max( f(i-1,j-v[i]) ,...f(i-1,j-s*v[i])+(s-1)*w[i],f(i-1,j-(s+1)*v[i])+s*w[i])
尝试失败
二进制优化数量
单调队列优化体积
二进制优化
假设第i种物品有s[i]个，将若干个第i种物品打包放一块儿考虑
比如1023个物品分为10组，每组各有1,2,4,8...512个物品，每一组要么一起选，要么都不选
类似01背包问题，经分析可知，我们可以用这十组拼凑出1023的任意一个数，
这样原来需要枚举1024次，现在只需要枚举10次
第i种物品有s[i]个，先拆分成logs[i]组，对于每一组用01背包问题去解决
时间复杂度：NVS->NlogS V=NVlogS
*/
//二进制做法 二维
#include<iostream>
#include<algorithm>
using namespace std;
//原来N表示多少种物品，现在N表示总共有多少组物品，所以N=n范围*logS范围
const int N=110010,M=2010;
int n,m;
int v[N],w[N];//存放每一组物品的总共的体积与价值
int f[N];//直接优化到01背包问题的一维
int main(){
cin>>n>>m;//表示多少种物品与背包的容量
int cnt=0;//表示有多少组物品
for(int i=1;i<=n;i++){
int a,b,s;
cin>>a>>b>>s;//输入当前这一种物品的体积，价值与个数
int k=1;//从1开始分组，每一组有k个物品
while(k<=s){
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0) {
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;//此时n表示当前有多少组
for(int i=1;i<=n;i++){//这儿不能改成从0开始，因为w[i]从下标1开始
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
//下标从0开始
#include<iostream>
using namespace std;
const int N=110010,M=2010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin>>n>>m;
int cnt=0;
for(int i=0;i<n;i++){
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s){
v[cnt]=a*k;
w[cnt]=b*k;
cnt++;
s-=k;
k*=2;
}
if(s>0) {
v[cnt]=a*s;
w[cnt]=b*s;
cnt++;
}
}
n=cnt;
for(int i=0;i<n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
//代码优化
#include <iostream>
using namespace std;
const int N = 2010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k <= s; k *= 2)
{
for (int j = m; j >= k * v; j -- )
f[j] = max(f[j], f[j - k * v] + k * w);
s -= k;
}
if (s)
{
for (int j = m; j >= s * v; j -- )
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
cout << f[m] << endl;
return 0;
}
AcWing 6. 多重背包问题 III(单调队列优化)
/*
完全背包：求所有前缀最大值，单独用一个变量维护前缀最大值
多重背包：求滑动窗口最大值 单调队列优化 (注意要加不同的偏移量)
二进制优化数量
单调队列优化体积
状态转移方程
f[j]=max(f[j],f[j-v]+w,f[j-2*v]+2*w,...f[j-k*v]+k*w);
在余数相同的这一类里面，这些数是连续的，所以算j时，是在前k个数中挑最大值
f[j+v]=max(f[j+v],f[j]+w,f[j-v]+2w,...f[j-(k-1)*v]+k*w);
算j+v时，可以看成是把长度为k的框往后移动一位,此时很像经典的单调队列滑动窗口问题
但有一点区别,算j+v时,与j相比，每个数都会加w,但其实这里不影响最大值,因为每一个数加上相同的数不影响相互之间的大小关系
转化
f[j+v]=max(f[j+v]-w,f[j],f[j-v]+w,...f[j-(k-1)*v]+(k-1)*w) +w;
...
f[j+k*v]时,max中先减去k*w,最后max外面再加上k*w,max中的是入队元素,计算状态时需要把w加上
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m;
int f[N], g[N], q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j ++ )
//循环体积时，把体积归类，j%v为0,1,2...各自归为一类,自此归为v类,相互独立
//状态转移时j从j-k*v转移过来的,也就是说从余数相同的前一个数转移过来，所以分别考虑每一类
{//枚举余数之后，余数相同的一类单独考虑
int hh = 0, tt = -1;
for (int k = j; k <= m; k += v)
{
if (hh <= tt && q[hh] < k - s * v) hh ++ ;
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
q[ ++ tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
//g[q[hh]] + (k - q[hh]) / v * w是g[q[hh]] - (q[hh] - j) / v * w + (k - j) / v * w的简化
}
}
}
cout << f[m] << endl;
return 0;
}
AcWing 1019. 庆功会
#include <iostream>
using namespace std;
const int N = 6010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
for (int j = m; j >= 0; j -- )
for (int k = 0; k <= s && k * v <= j; k ++ )
f[j] = max(f[j], f[j - k * v] + k * w);
}
cout << f[m] << endl;
return 0;
}
#include <iostream>
using namespace std;
const int N = 6010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k <= s; k *= 2)
{
for (int j = m; j >= k * v; j -- )
f[j] = max(f[j], f[j - k * v] + k * w);
s -= k;
}
if (s)
{
for (int j = m; j >= s * v; j -- )
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
cout << f[m] << endl;
return 0;
}
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 6010;
int n, m;
int f[N], g[N], q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j ++ )
{
int hh = 0, tt = -1;
for (int k = j; k <= m; k += v)
{
if (hh <= tt && q[hh] < k - s * v) hh ++ ;
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
q[ ++ tt] = k;
f[k] = g[q[hh]] - (q[hh] - j) / v * w + (k - j) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}
AcWing 9. 分组背包问题
//与01背包问题类似，分组背包问题可按照第i组物品不选，或者选第1,2…si个去分类
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int f[N][N]; //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N]; //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j]; //读入
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j]; //不选
for(int k=0;k<s[i];k++){
if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m]<<endl;
}
//与01背包问题类似，分组背包问题可按照第i组物品不选，或者选第1,2…si个去分类
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];//直接一维优化版本
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )//i=0,i<n也行
{
cin >> s[i];
for (int j = 0; j < s[i]; j ++ )
cin >> v[i][j] >> w[i][j];
}
//如果转移时候用的是上一层(本层)的状态，就从大到小(从小到大)枚举体积
for (int i = 1; i <= n; i ++ )//i=0,i<n也行
for (int j = m; j >= 0; j -- )//从大到小
for (int k = 0; k < s[i]; k ++ )
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}
AcWing 1013. 机器分配
/*
每个公司看作一组物品，每个公司不同的方案看作这组物品中的不同物品
机器总数量看作背包最大容量
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 11, M = 16;
int n, m;
int w[N][M];
int f[N][M];//二维是因为要求方案，不然直接一维优化即可
int way[N];//记录方案
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> w[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= j; k ++ )
f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
cout << f[n][m] << endl;
int j = m;//之前求具体方案那道题因为题目要求字典序，所以要从前往后遍历，这道题不用，从后往前即可
for (int i = n; i; i -- )
for (int k = 0; k <= j; k ++ )
if (f[i][j] == f[i - 1][j - k] + w[i][k])
{
way[i] = k;
j -= k;
//cout << i << ' ' << way[i] << endl;//不按照字典序输出
break;
}
//按照字典序从小到大输出
for (int i = 1; i <= n; i ++ ) cout << i << ' ' << way[i] << endl;
return 0;
}
AcWing 10. 有依赖的背包问题
/*
背包问题+树形DP
状态表示：f(i,j)
集合：选节点i，总体积不超过j的情况下，整棵子树的最大收益
分组背包，i的每个子节点是一个物品组，每个子节点的不同体积也就是不同选择方案代表组内的物品
选课是这个问题的很好的背景，每门课有对应的先修课需要选，每门课有各自的收益，精力
有限，选哪些课受益最大
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int n,m;
int h[N],e[N],ne[N],idx;
int v[N],w[N],f[N][N];
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u){//分组背包问题
for(int i = h[u];i!=-1;i = ne[i]){//对当前结点的边(子树)进行遍历,先循环物品组
int son = e[i];//e数组的值是当前边的终点，即儿子结点
dfs(son);
for(int j = m-v[u];j>=0;j--){//循环体积。
for(int k = 0;k<=j;k++){//循环决策
f[u][j] = max(f[u][j],f[u][j-k]+f[son][k]);
}
}
}
//加上刚刚默认选择的父节点价值
for(int i = m;i>=v[u];i--){
f[u][i] = f[u][i-v[u]]+w[u];
}
//因为我们是从叶子结点开始往上做，所以如果背包容积不如当前物品的体积大，那就不能选择当前结点及其子节点，因此赋值为零
for(int i = 0;i<v[u];i++){
f[u][i] = 0;
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
int root;
for(int i = 1;i<=n;i++){
int p;//每个点依赖的点
cin>>v[i]>>w[i]>>p;
if(p==-1){
root = i;
}else{
add(p,i);//如果不是根节点就加入邻接表,其中p是该节点的父节点，i是当前是第几个节点
}
}
dfs(root);
cout<<f[root][m]<<endl;
return 0;
}
AcWing 487. 金明的预算方案
/*
可以将每个主件及其附件看作一个物品组，记主件为p，两个附件为a,b，则最多一共有4种组合：
p
p,a
p,b
p,a,b
这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题
*/
#include <cstring>
#include <iostream>
#include <vector>
#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;
const int N = 70, M = 32010;
int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i ++ )
{
int v, p, q;
cin >> v >> p >> q;
p *= v;
if (!q) master[i] = {v, p};
else servent[q].push_back({v, p});
}
for (int i = 1; i <= n; i ++ ){
if(master[i].v){
for (int u = m; u >= 0; u -- )
{
for (int j = 0; j <1 << servent[i].size(); j ++ )
{//用二进制枚举不同的选法
int v = master[i].v, w = master[i].w;
for (int k = 0; k < servent[i].size(); k ++ )
if (j >> k & 1)
{
v += servent[i][k].v;
w += servent[i][k].w;
}
//求得当前这种选法，也就是这一组物品的这个物品的体积与价值
if (u >= v) f[u] = max(f[u], f[u - v] + w);
}
}
}
}
cout << f[m] << endl;
return 0;
}
AcWing 7. 混合背包问题
/*
不管哪种背包问题，状态表示都一的，只是转移方程不同，所以混合背包问题只需要根据第i种物品的类型判断使用哪种转移方程
*/
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
if (!s)//完全背包问题
{
for (int j = v; j <= m; j ++ )
f[j] = max(f[j], f[j - v] + w);
}
else
{//01背包是一种特殊的多重背包
if (s == -1) s = 1;//二进制优化
for (int k = 1; k <= s; k *= 2)
{
for (int j = m; j >= k * v; j -- )
f[j] = max(f[j], f[j - k * v] + k * w);
s -= k;
}
if (s)
{
for (int j = m; j >= s * v; j -- )
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
}
cout << f[m] << endl;
return 0;
}
状态机模型
AcWing 1049. 大盗阿福
/*
f[i]表示抢劫前i个店铺的最大收益，因此根据第i家店铺抢或不抢划分
f[i]=max(f[i−1],f[i−2]+w[i])
*/
#include<iostream>
using namespace std;
const int N=100010;
int f[N];
int main()
{
int T;
cin>>T;
while(T --)
{
int n;
cin>>n;
int w;
cin>>w;
f[1] = w;
for(int i = 2; i <= n; i ++)
{
cin>>w;
f[i] = max(f[i - 1], f[i - 2] + w);
}
cout<<f[n]<<endl;
}
return 0;
}
/*
状态机特点：描述的是一个过程而不是一个结果
背包问题中，第i件物品选或不选只有一步，从开始到结束没有任何中间过程
但比如卖股票这道题，交易一次，先买入再卖出中间可能经过很多时间，整个过程才是一个完整的事件
一系列有序的事件，状态机可以把事件的各个状态描述清楚
有哪些状态，状态之间可以怎样转换
状态计算时需要引入状态这个概念，之前只需要一个状态，这里把一个状态拆成若干个过程
状态机思路，希望状态转移时只依赖上一层状态
引入两个状态，把每个f(i)分解成两个状态f(i,0)和f(i,1)表示这家店铺抢或不抢
0 1这两个状态之间可以相互转换
如果当前这家店铺处于0状态，不抢，则下一个店铺可抢可不抢
如果当前这家店铺处于01态，抢，则下一个店铺一定不抢
两个点，三条边，每一步走一条边，一个入口，两个出口
任何一个抢劫方案都可以对应到状态机的长度是n一个走法
反过来任意一个长度是n一个走法都可以对应一个抢劫方案
当状态不好表示时，用状态机形式把不好表示的状态分离开，状态压缩DP思想类似
状态表示：
集合：所有走了i步，且当前位于状态j的所有走法
属性：max
状态计算：
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];
*/
#include<iostream>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int n;
int w,f[N][2];
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
f[0][0]=0,f[0][1]=-INF;
for(int i=1;i<=n;i++){
cin>>w;
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=f[i-1][0]+w;
}
int res=0;
res=max(f[n][0],f[n][1]);
cout<<res<<endl;
}
return 0;
}
AcWing 1057. 股票买卖 IV
/*
状态机分析过程类似图论建模
1.明确有几个状态作为节点
2.明确这几个节点能够怎样相互转换，并给他们连上带权值的有向边（包括自环）（权值可能为0，可能为正数或负数）
3.根据每个节点的入度写状态转移方程
状态表示：
f(i,j,0/1)表示股票交易进行到了第i天，已经进行了k次交易，此时手中有无股票
其中对于j更准确的说法是已经进行了j次交易或者正在进行第j次交易，股票还未卖出
状态计算：
有两个状态，当前有无股票
如果当天没有股票，则第二天可以选择什么都不做，状态不变，或者在第二天把股票买入（钱变少），变成有股票状态
如果当天有股票，则第二天可以选择什么都不做，状态不变，或者在第二天把股票卖出（钱变多），变成无股票状态
f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]+w[i]);
f[i][j][1] = max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
两个节点，四条边，边表示钱的变化，一个入口，一个出口
*/
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10,M=110,INF=0x3f3f3f3f;
int n,m;
int w[N];
int f[N][M][2];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
memset(f,-INF,sizeof f);//状态不合法，不希望从这个状态转移过来
for(int i=0;i<=n;i++) f[i][0][0]=0;
// for(int i=0;i<=n;i++) f[i][0][1]=-INF;两者选一个初始化
// for(int i=0;i<=n;i++) f[0][i][1]=-INF;
// for(int i=1;i<=n;i++) f[0][i][0]=-INF;
// for(int i=0;i<=n;i++) f[i][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){//j也要从1开始，因为用到了j-1
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
}
}
int res=0;
for(int i=0;i<=m;i++) res=max(res,f[n][i][0]);
cout<<res<<endl;
return 0;
}
AcWing 1058. 股票买卖 V
/*
状态表示：
三个顶点，五条边，一个入口，两个出口
f[i][0]表示第i天手里有股票
f[i][1]表示第i天是手里没有股票的第一天
f[i][2]表示第i天是手里没有股票的第大于等于2天
状态计算：
f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
f[i][1] = f[i - 1][0] + w[i];
f[i][2] = max(f[i - 1][2], f[i - 1][1]);
*/
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][3];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>w[i];
//memset(f,-INF,sizeof f);加不加都ac
f[0][0] = f[0][1] = -INF, f[0][2] = 0;
for (int i = 1; i <= n; i ++ )
{
f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
f[i][1] = f[i - 1][0] + w[i];
f[i][2] = max(f[i - 1][2], f[i - 1][1]);
}
cout<<max(f[n][1], f[n][2]);
return 0;
}
AcWing 1052. 设计密码
/*
|T|+1个状态自动机
给定子串str长度为m，kmp思路就是一根指针j一直往前走，匹配就继续往前，不匹配就往后回退
直到最开始为止
这道题把能跳到的所有位置看成状态，从0到m一共有m+1个状态，入口为第0个状态
不包含子串T即kmp匹配过程指针j不能跳到终点状态m
匹配过程中j最终能跳到哪儿取决于j+1尝试匹配的i是哪个字母，对于每个点(状态)都有26条边
可能有重边，但无所谓
所以我们完全可以枚举第i个位置放'a'的时候，j跳到哪儿，放'b'的时候跳到哪儿......
这样我们就建出m+1个点，26条边的状态转移图
入口为状态0，匹配过程中每步沿着边走(每走一步就代表多确定一个密码中的字符)，
限制是总共走N步，最终不能走到状态m的情况下，最终有多少条不同路线
每一个合法的密码都能对于这样一条路线，所以合法密码数量等价于满足要求的路线数量，
状态表示：
f[i][j]表示的是在长度为i的的所有字符串中 使得我们的模式串最终跳到位置j的字符串总数
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 55;
const int mod = 1e9 + 7;
int f[N][N];
int trans[N][26];
char p[N];
int n, ne[N];
int main()
{
cin >> n >> p + 1;
int m = strlen(p + 1);
for (int i = 2, j = 0; i <= m; i++) {//求next数组
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
//预处理过程，预先存储j在每个位置上,j+1尝试匹配的i确定的情况下，j最终转移到哪儿
for (int j = 0; j < m; j++) {//不能等于，这样就完全匹配了
for (int k = 'a'; k <= 'z'; k++) {
int u = j;
while (u && p[u + 1] != k) u = ne[u];
if (p[u + 1] == k) u++;
trans[j][k - 'a'] = u;
//trans矩阵代表当模式串位置在j时并且当前主串为字母k的时候 下一次会转移到哪个位置
}
}
f[0][0] = 1;
//i是从第0个字母开始填，填到第i个字母，此时密码子串匹配到j
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j ++) {
for (char k = 'a'; k <= 'z'; ++k)
{
int u = trans[j][k - 'a'];//此时填到第i+1个字母时，密码子串匹配到u
if (u < m) f[i+1][u] = (f[i+1][u] + f[i][j]) % mod;
//f[i+1][u]表示的当开始填第i+1个字母的时候，密码子串匹配到u的字符串总数。
//它正是由填到第i个字母时，密码子串匹配到j的字符串中那些下一次匹配可以转移到u的位置所转移过来的
}
}
}
int ans = 0;
for (int i = 0; i < m; ++i) ans = (ans + f[n][i]) % mod;
cout << ans << endl;
return 0;
}
状态压缩DP
AcWing 1064. 小国王
/*
状态压缩DP：
1.棋盘式（基于连通性）:题目描述是一个棋盘，在棋盘中统计一些值(方案数，最小数量)
2.集合式（每个元素是否在集合内）
蒙德里安的梦想那道题中连通性是1*2的小方格，这里的连通性是一个井字型，玉米田是一个十字形
暴力枚举较多，考虑DP，DP本质是用一个状态表示一类方案，这样就不用考虑每个方案，而是考虑集合之间的递推关系
摆放某一行时，怎么样放只跟上一行状态有关系，与上上行无关，所以可以把每一行的不同状态看成一类，用一个集合表示
与状态机有相似之处，用一维f(i)表示前i行无法表示时，把第i行状态分解
状态机根据时序分解，当前这个时刻怎么样，下一个时刻怎么样
状态压缩DP根据二进制或者集合思想把状态分解掉
状态表示：
f(i,s)由于有棋子限制->f(i,j,s)
集合：所有摆到第i行，第i行已经摆完了，已经放了j个棋子，并且第i行的状态是s的方案的集合
每一行的状态s用二进制表示
属性：数量
状态计算：
划分依据是找到最后一个不同点，根据上一行状态分类
1.首先上一行状态得合法，即第i-1行内部不能有两个1相邻
2.其次能成功转移过来，两行不能相互攻击到
a&b==0(否则上下两行同一列都存在国王)
a|b不能有两个相邻的1(否则对角线能够互相攻击到)
f[i][j][a]:表示已经摆完了前i行，放了j个棋子，并且第i行的状态是a
f[i - 1][j - c][b]:表示已经摆完了前i-1行，放了j-count(a)个棋子，并且第i-1行的状态是b
上一行状态f[i - 1][j - c][b]只要确定，那下一行状态f[i][j][a]也就唯一确定，所以累加即可
f[i][j][a] += f[i - 1][j - c][b]; 当然上一行的状态的满足以上两个限制
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;//N：棋盘大小 M：状态 K：国王数量
int n, m;
vector<int> state;//存储所有合法状态
int cnt[M];//每个状态1的个数，也就是每个状态放了多少国王
vector<int> head[M];//每个状态可以由哪些状态转移到
LL f[N][K][M];//状态矩阵
bool check(int state)
{//检查当前状态是否合法，也就是状态中是否有连续的1
for (int i = 0; i+1 < n; i ++ )
//遍历当前状态的倒数第0位至倒数第n-2位，如果如果第i位和第i+1位都是1，此状态不合法
if ((state >> i & 1) && (state >> i + 1 & 1))//state >> i & 1用来判断状态state中倒数第i位是否为1
return false;
return true;
}
int count(int state)
{
int res = 0;//遍历当前状态的倒数第0位至倒数第n-1位
for (int i = 0; i < n; i ++ ) res += state >> i & 1;
return res;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < 1 << n; i ++ )
if (check(i))//枚举所有状态，确定其中哪些状态是合法的
{
state.push_back(i);
cnt[i] = count(i);//计算此合法状态有多少个1，也就是放了多少个国王
}
for (int i = 0; i < state.size(); i ++ )
for (int j = 0; j < state.size(); j ++ )
{//预处理任意两个状态之间的转移，记录合法的状态转移
int a = state[i], b = state[j];
if ((a & b) == 0 && check(a | b))
//前者表示上下两行的同一列不存在都为1的情况，后者在前者的基础上表示对角线上不存在都为1的情况
head[i].push_back(j);//此时第i个状态能由第j个状态合法转移过来，这里的ij是下标
}
f[0][0][0] = 1;//最初没放国王也是一种合法的方案，所以初始化为1
for (int i = 1; i <= n + 1; i ++ )
//从第1行放到第n+1行，+1是因为我最后要计算的是放完了n+1行，放了m个国王，第n+1行的状态为0的方案数
for (int j = 0; j <= m; j ++ )
//当前到这一行为止，前面总共放了多少个国王可能一个也没放，也可能放了全部国王
for (int a = 0; a < state.size(); a ++ )//枚举所有合法状态，从第0个状态开始往后枚举
for (auto b : head[a])//枚举当前的第a个状态能由哪些状态能转移到
{
int c = cnt[state[a]];//表示当前这一行放了多少个国王
if (j >= c) f[i][j][a] += f[i - 1][j - c][b];//可以转移
}
cout << f[n + 1][m][0] << endl;
return 0;
}
AcWing 327. 玉米田
/*
与上一题基本差不多，区别是周围八个不能放变四个，以及一些格子不能放，最后是没有个数限制
同样，摆放某一行时，怎么样放只跟上一行状态有关系，与上上行无关
状态表示：f(i,s)
集合：所有摆完了前i行，且第i行的状态为s的所有摆放方案的集合
属性：数量
状态计算：
f[i][j] += f[i - 1][k]//+的前提是上一行状态合法且上一行能转移到当前行
上一行状态合法：当前状态没有连续的1且种植玉米的地方是可以种的
上一行能转移到当前行：只需要上下两行在同一列不能都为1也就是只需(j&k)==0即可，没有上道题的对角线限制
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 14, M = 1 << 12, mod = 1e8;
int n, m;
int w[N];//存储每一行的初始状态s，用来判断这一行哪些土地可种植可不种植
vector<int> state;//存储所有合法状态
vector<int> head[M];//记录哪些状态转移合法
int f[N][M];//状态矩阵
bool check(int state)
{
/*
这道题而言，check函数更准确的说是用来判断当前这个状态是否合法的一部分：是否有相邻的1
对于田地不育的合法性是用状态计算过程中来判断
*/
for (int i = 0; i+1< m; i ++ )
if ((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < m; j ++ )
{
int t;
cin >> t;
//如果输入t为0也就是当前土地不育，将当前第i行的倒数第j个位置取反置为1，这样方便最后做与运算
w[i] += (!t << j);//这里取反完全是因为输入的表示
}
for (int i = 0; i < 1 << m; i ++ )
if (check(i))//枚举所有状态，存入所有合法状态
state.push_back(i);
for (int i = 0; i < state.size(); i ++ )
for (int j = 0; j < state.size(); j ++ )
{//枚举任意两个状态，如果第i个状态能由第j个状态转移过来，存入
int a = state[i], b = state[j];
if ((a & b)==0)//这里不要多想，跟w搞混，，状态中某一位为1只表示这个地方种植了玉米
head[i].push_back(j);
}
f[0][0] = 1;//初始化
for (int i = 1; i <= n + 1; i ++ )//枚举所有状态，注意枚举到第n+1行
for (int j = 0; j < state.size(); j ++ )//枚举当前第i行处于第j个状态
if ((state[j] & w[i])==0)//表示当前第i行没有在不育的土地种植玉米，在这一行第j个状态确认合法
for (int k : head[j])
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;//计算过程中注意取模
cout << f[n + 1][0] << endl;
return 0;
}
AcWing 292. 炮兵阵地
/*
与上一题区别是相邻一格变两格，所求从多少种方案变成了最多摆放数量，属性由count变成max
状态表示：f(i,j,k)
集合：所有已经摆完前i行，且i-1行的状态是j，第i行的状态是k的所有方案的最大值
属性：max
状态计算：
合法状态
i-1:a i:b i-2:c
(a&b)|(a&c)|(b&c)==0 abc两两之间不能都为1
(g[i-1]&a|g[i]&b)==0 (&优先级大于|)
炮只能放在平地上，不能放在山地上，这也要求输入时，如果第i行倒数第j列为字符h，需要将这一位置为1
g[i] += (c == 'H') << j;
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int M = 1 << 10;
int n, m;
int g[110];
int f[2][M][M];//空间限制较大，用滚动数组来做，否则超内存，很简单，先正常写，然后第一维&1即可
vector<int> state;//存储所有合法状态
int cnt[M];//这道题需要求最多数量，所有要单独记录合法状态的摆放数量
bool check(int state)
{
for (int i = 0; i < m; i ++ )
if ((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1)))
//倒数第i位为1，且倒数第i+1位，倒数第i+2位中任意为1均不合法
return false;
return true;
}
int count(int state)
{
int res = 0;
for (int i = 0; i < m; i ++ )
if (state >> i & 1)
res ++ ;
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < m; j ++ )
{
char c;//定义时注意，y总debug了很久
cin >> c;
g[i] += (c == 'H') << j;
}
for (int i = 0; i < 1 << m; i ++ )
if (check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
for (int i = 1; i <= n+2; i ++ )
for (int j = 0; j < state.size(); j ++ )//i-1
for (int k = 0; k < state.size(); k ++ )//i
for (int u = 0; u < state.size(); u ++ )//i-2
{
int a = state[j], b = state[k], c = state[u];
if (a & b | a & c | b & c) continue;
if (g[i] & b | g[i - 1] & a) continue;//这道题不需要单独计算状态转移
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
//&1是因为这里是滚动数组
}
cout << f[n+2&1][0][0] << endl;//滚动数组要&1，别漏了
return 0;
}
AcWing 291. 蒙德里安的梦想
/*
状态压缩DP，就是用二进制数保存状态。为什么不直接用数组记录呢？
因为用一个二进制数记录方便作位运算。前面做过的八皇后，八数码，也用到了状态压缩。
本题等价于找到所有横放 1 X 2 小方格的合法方案数，因为所有横放确定了，那么竖放方案是唯一的。
如何判断方案是否合法：所有剩余位置能否填满竖着的小方块，所有每一列内部连续的空着的小方块需要是偶数个
状态表示：
用f[i][j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的状态是j的方案数。
j状态二进制表示中某一位等于1表示在这一行上一列有横放格子，本列有格子捅出来。
状态计算：
本列的每一个状态都由上列所有“合法”状态转移过来，上一列的合法方案一旦确定，本列的摆放也确定。
所以说第i列状态j的方案数为上一列也就是i-1列所有能合法转移到状态j的状态k的方案累加
f[i][j] += f[i - 1][k]
两个转移条件：
同一行的第 i 列和第i - 1列不同时捅出来 ；
本列捅出来的状态j和上列捅出来的状态k求或，得到上列的每个格子是否被占用的状态，如果上一列是奇数空行状态，则不转移。
初始化条件f[0][0] = 1，第0列只能是状态0，无任何格子捅出来。返回f[m][0]。第m + 1列不能有东西捅出来。
时间复杂度：先枚举每一列，再枚举每一列的每种状态，再枚举上一列的每种状态来找到合法的状态转移
11*2^11*2^11
优化：
预处理对于每一个状态j，上一列有哪些状态k可以合法更新到j，所以可以少遍历一层循环
*/
#include <cstring>//memset函数需要引入这个头文件
#include <iostream>
#include <algorithm>
#include<vector>//存储合法转移状态
using namespace std;
const int N = 12, M = 1 << N;//N为12是因为会遍历到n+1列，最多为12，M表示有多少种状态
int n, m;
long long f[N][M];//方案数较大，用long long存
bool st[M];//表示每一种状态转移是否合法
//第i列状态为j，第i-1列状态为k，j|k表示这种状态转移情况下第i-1列每个格子的被占用情况，1表示被占用
vector<int> state[M];//表示每一种状态可以由哪些状态合法转移过来，这是用于优化的预处理过程
int main()
{
while (cin >> n >> m, n || m)
{
//枚举哪些状态转移是合法的
for (int i = 0; i < 1 << n; i ++ )//一共n行，每个格子是否被占用，枚举2^n种不同的状态
//0表示00..0(n个0)初始状态，i < 1 << n表示11...1(n个1)最终状态
{
int cnt = 0;//用来记录连续的0的个数
st[i] = true;//记录这个状态被枚举过且可行
for (int j = 0; j < n; j ++ )//从低位到高位枚举它的每一位
if (i >> j & 1)//如果状态i的二进制表示中第j位为1的话
{
if (cnt & 1) st[i] = false;//如果之前连续0的个数是奇数，竖的方块插不进来，这种状态不行
cnt = 0;//清空计数器
}
else cnt ++ ;//如果不为1，计数器+1
//前面判断每一列是否合法是通过找到状态为1的格子，判断它之前的cnt是否为奇数，但如果这一列中一直没有状态为1的格子呢
//所以最后再加一个判断
if (cnt & 1) st[i] = false;//到末尾再判断一下前面0的个数是否为奇数，同前
}
// for(int i=0; i<1<<n ;i++){//枚举每一种状态可以由哪些状态合法转移过来
// state[i].clear();
// for(int j=0;j<1<<n;j++){//暴力枚举所有可以尝试转移到i的状态
// if((i&j)==0&&st[i|j])
// state[i].push_back(j);
// }
// }
memset(f, 0, sizeof f);//一定要记得初始化成0，对于每个新的输入要重新计算f[N][M]
f[0][0] = 1;//其他第0列的状态都为0
for (int i = 1; i <= m; i ++ )//对于每一列
for (int j = 0; j < 1 << n; j ++ )//枚举j的状态
// for (auto k:state[j] )//遍历能转移到状态j的合法状态
// f[i][j] += f[i - 1][k];//那么这种状态下它的方案数等于之前每种k状态数目的和
for (int k = 0; k < 1 << n; k ++ )//优化之前
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;//求的是第m行排满，并且第m行不向外伸出块的情况
}
return 0;
}
AcWing 91. 最短Hamilton路径
/*
两个关键因素：哪些点被遍历过，当前停留在哪个点上
状态表示：
f(i,j) 表示状态是i，此时停在点j的最短路径
i表示经过哪些点，对应的二进制表示上哪一位为1就代表这一点被遍历过了
j表示当前到达了j点
状态计算：
根据由哪一个点达到j分类
f(state,j)=min( f(state_k , k) + w[k][j] ) state_k表示除掉j，包含k的集合
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
cin >> w[i][j];
memset(f, 0x3f, sizeof f);//状态全部初始化为正无穷，以便于取最小值
f[1][0] = 0;//初始时刻只在0号点，所以只经过了0号点，停留在0号点上
for (int i = 0; i < 1 << n; i ++ )
for (int j = 0; j < n; j ++ )
if (i >> j & 1)//从0走到j的话，i中一定得包含j，也就是第j位为1
for (int k = 0; k < n; k ++ )//枚举从哪儿转移到状态j
if (i >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
cout << f[(1 << n) - 1][n - 1];//所有点都走过来，最后停留在点n-1
return 0;
}
区间DP
AcWing 282. 石子合并
/*
注意这里要求合并的是两堆相邻的石子，所以要考虑区间DP问题，不然这道题是典型的贪心问题
区间DP：状态表示某一个区间
状态表示：
f(i,j)表示区间[i,j]也就是所有合并第i堆到第j堆石子的方法中的最小代价
最后所求为f(1,n)
状态计算：
集合划分 按照最后合并两堆的分界线k分类，也就是最后合并的两堆为
(l,k)和(k+1,r)
k=l,....,r-1(因为要求最后两个待合并的区间非空，所有k最小取l，最大取r-1)
所以f(l,r)=min( f(l,k) + f(k+1,r) + l到r的前缀和也就是s[r]-s[l-1])
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n;
int s[N];//前缀和数组
int f[N][N];//状态数组
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>s[i];
//初始化前缀和数组
for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
//len表示区间中有多少个元素，外层循环枚举区间长度从2开始
//len=1时代价为0，在这道题中，状态数组的边界情况不用特意初始化
for (int len = 2; len <= n; len ++ )
//内层循环枚举区间左端点
for (int i = 1; i + len - 1 <= n; i ++ )
{
int l = i, r = i + len - 1;
f[l][r] = 1e8;//取最小值，要先初始化为最大值
for (int k = l; k < r; k ++ )
//这里k表示左区间[l,k]的右端点，要保证两个区间非空，所以k可以去到l，不能为r
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout<<f[1][n];
return 0;
}
AcWing 1068. 环形石子合并
/*
与石子合并类似，只是把一维扩展到环形
朴素想法：
n个石子环形排列，两个石子合并连一条边，最后n个石子合并连n-1条边，必然有一个缺口，所以可以枚举缺口，将环形变为一维
时间复杂度：n^3*n=n^4(不可取)
每一条边断开就是一条链，所以本质上是要求n条长度为n的一维石子合并问题
经典做法：
先把n个石子组成的环展开，然后再复制一遍得到一条长度是2n的链(1,2,3,4,...,n-1,n,1,2,3,4,...,n-1,n)
这样所要求的的n条长度为n的链都在这条长度为2n的链上
所以可以对这条长度为2n的链做一维石子合并问题，这样预处理出来这条链上所有区间的最小值，然后再枚举所有长度是n的区间
从而得到要求的n种情况
时间复杂度：(2n)^3=8n^3(可取)
区间问题两种实现方式：
迭代式
for(int len=1;len<=n;len++)//第一维循环长度
for(int l=1;l+len-1<=n;l++)//第二维循环左端点
r=l+len-1
记忆化搜索式
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 410, INF = 0x3f3f3f3f;//最多200堆石子，开两倍
int n;
int w[N], s[N];
int f[N][N], g[N][N];//两个状态数组，因为要求最大值和最小值
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> w[i];//输入n堆石子，边输入边复制
w[i + n] = w[i];
}
for (int i = 1; i <= n * 2; i ++ ) s[i] = s[i - 1] + w[i];//前缀和数组处理
for (int len = 2; len <= n; len ++ ){//不用循环到2n，因为用不到，枚举的区间长度最多为n即可
for (int i = 1; i + len - 1 <= 2*n; i ++ )//枚举左右端点
{
int l = i, r = i + len - 1;
f[l][r] = INF;//求最小值必须初始化，因为都为正整数，必然都大于0，不初始化的话结果为0
//g[l][r]=-INF;//求最大值可以不初始化，因为都为正整数，必然都大于0，不初始化结果也正确
for (int k = l; k < r; k ++ ){//枚举分界线
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
int minv = INF, maxv = -INF;
for (int i = 1; i <= n; i ++ )
{//枚举所有长度为n的子区间
minv = min(minv, f[i][i + n - 1]);
maxv = max(maxv, g[i][i + n - 1]);
}
cout << minv << endl << maxv << endl;
return 0;
}
AcWing 320. 能量项链
/*
可以把每个珠子看成一个矩阵，头尾标记看作矩阵的行数与列数，两颗珠子合并可以看成两个矩阵相乘
状态表示：f(l,r)
集合：所有将(l,r)合并成一个矩阵（颗珠子）的方式
属性：max
状态计算：
根据若干个矩阵相乘的分界线分为若干个子集
分界线：l+1,...r-1
(l,k) (k,r) 注意这里的分界线k是公用的 先合并(l,k) 再合并(k,r) 最后整个合并，也就是l*k*r
线性做法就是每一类取最大值即可
最后会将所有矩阵合并为一个(wi,wi)的矩阵，这取决于从哪一点开始断开，所给样例可以断开成一条五个点的链，可以枚举断开哪个点从而形成这条链
最终方案一定是断开某个点之后的结果
例子：输入：2 3 5 10 四颗珠子（四个矩阵）：(2,3),(3,5),(5,10),(10,2)
可以表示成从2开头的5个数：2 3 5 10 2 最后合并成(2,2)
也可以表示成从3开头的5个数：3 5 10 2 3 最后合并成(3,3)
类似...
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> w[i];
w[i + n] = w[i];
}
for (int len = 3; len <= n + 1; len ++ )//最少合并两个相邻矩阵，也就是三个数
for (int l = 1; l + len - 1 <= n * 2; l ++ )
{
int r = l + len - 1;//因为求最大值，且都为正整数，所以不初始化也没事
for (int k = l + 1; k < r; k ++ )
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
int res = 0;
for (int l = 1; l <= n; l ++ ) res = max(res, f[l][l + n]);
cout << res << endl;
return 0;
}
AcWing 479. 加分二叉树
/*
对于中序遍历，根节点可能在任何一个地方，左子树在根节点左边，右子树在根节点右边
(区间DP,二叉树的遍历) O(n^3)
状态表示：f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。
状态计算：f[i][j] = max(f[i][k - 1] * f[k + 1][j] + w[k])，即将f[i][j]表示的二叉树集合按根节点分类，
则根节点在 k 时的最大得分即为 f[i][k - 1] * f[k + 1][j] + w[k]，则f[i][j]即为遍历 k 所取到的最大值。
这里的分界点k可以是i到j的任意一个数
在计算每个状态的过程中，记录每个区间的最大值所对应的根节点编号。
那么最后就可以通过DFS求出最大加分二叉树的前序遍历了。
时间复杂度
状态总数是 O(n^2)，计算每个状态需要 O(n) 的计算量，因此总时间复杂度是 O(n^3)。
*/
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n;
int w[N];
int f[N][N], g[N][N];//前者是状态矩阵，后者记录根节点编号
void dfs(int l, int r)
{
if (l > r) return;
int k = g[l][r];
cout << k << ' ';
dfs(l, k - 1);
dfs(k + 1, r);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int len = 1; len <= n; len ++ )//区间dp一般先循环区间长度再循环区间左端点
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;
if (len == 1) f[l][r] = w[l], g[l][r] = l;//只有一个点，根节点就是它自己
else
{
for (int k = l; k <= r; k ++ )
{//这里的分界点k为l到r的任意一个数
int left = k == l ? 1 : f[l][k - 1];//计算左右子树得分
int right = k == r ? 1 : f[k + 1][r];
int score = left * right + w[k];
if (f[l][r] < score)//这里只有严格大于的时候才更新二叉树，等于时候不会更新，也就是存的恰好是最左边的最大值
{//是否需要更新根节点与得分
f[l][r] = score;
g[l][r] = k;
}
}
}
}
cout << f[1][n] << endl;
dfs(1, n);//输出字典序最小的前序遍历，也就是保证输出的根节点编号最小，也就是在找分值最大的二叉树时，找最左边的最大值
return 0;
}
AcWing 1069. 凸多边形的划分
/*
状态表示：f(l,r)
集合：所有将(l,l+1),(l+1,l+2),...,(r-1,r),(r,l)这个凸多边形划分成个互不相交的三角形的方案
属性：min
状态计算：集合划分
划分依据：最终根据与l,r组成三角形的点k去划分
f[i][j]表示将[i,j]区间的划分成三角形的最小花费
f[i][j]=min(f[i][j],f[i][k]+f[k][j]+w[i]∗w[j]∗w[k])
需要用到高精度的话先不写高精度，最后需要高精度的地方改一下就行
*/
//不用高精度
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55, INF = 1e9;
int n;
int w[N];
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];//虽然看着是一个环形，但从任意一条边开始都是一样的，枚举一种情况即可
for (int len = 3; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;
f[l][r] = INF;
for (int k = l + 1; k < r; k ++ )
{
f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
}
cout<<f[1][n]<<endl;
return 0;
}
//高精度
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 51, INF = 1e9, M = 35;
typedef long long LL;
vector<int>f[N][N];
LL w[N];
void print(vector<int> & a)
{
for(int i = a.size() - 1; i >= 0; i--)
cout << a[i];
cout << endl;
}
vector<int> add(vector<int> a, vector<int> b)
{
vector<int> c;
if(a.size() < b.size())return add(b, a);
int t = 0;
for(int i = 0; i < a.size(); ++i)
{
t += a[i];
if(i < b.size())t += b[i];
c.push_back(t % 10);
t /= 10;
}
if(t) c.push_back(t);
return c;
}
void mul(vector<int> & a, LL b)
{
vector<int> c;LL t = 0;
for(int i = 0; i < a.size() || t > 0; ++i)
{
if(i < a.size())t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
a = c;
}
bool cmp(vector<int> &a, vector<int> &b)
{
int n = a.size(), m = b.size();
if(n != m)return n > m;
else
{
for(int i = n - 1; i >= 0; i--)
if(a[i] == b[i])continue;
else return a[i] > b[i];
}
}
int main()
{
int n; cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> w[i];
}
for(int len = 3; len <= n; ++len)
for(int l = 1; l + len -1 <= n; ++l)
{
int r = l + len - 1;
for(int i = 0; i < M; ++i)
f[l][r].push_back(1);
for(int k = l + 1; k < r; ++k)
{
vector<int> temp;
temp.push_back(w[l]);
mul(temp, w[k]);
mul(temp, w[r]);
// print(temp);
//print(f[l][k]);
temp = add(temp, f[l][k]);
//print(temp);
//cout << k << endl;
temp = add(temp, f[k][r]);
if(cmp(f[l][r], temp))
f[l][r] = temp;
//f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
}
print(f[1][n]);
return 0;
}
AcWing 321. 棋盘分割
/*
f[x1][y1][x2][y2][k]
状态表示：
集合：以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵切割成k部分的所有方案
属性：均方差最小
状态计算：
1）集合划分：
1.1) 横着切:
1.2) 竖着切:
2）状态转移方程
模拟上述集合的划分枚举所有的区间即可
由于dp的方程维数过大，写 5 重迭代太麻烦了，这题采用记忆化搜索
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>//由于要开方
using namespace std;
const int N = 15, M = 9;//最多切14刀，下标从0到8，所以开到9
const double INF = 1e9;
int n, m = 8;
int s[M][M];//二维前缀和
double f[M][M][M][M][N];//状态矩阵
double X;
int get_sum(int x1, int y1, int x2, int y2)
{
return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
double get(int x1, int y1, int x2, int y2)
{
double sum = get_sum(x1, y1, x2, y2) - X;
return (double)sum * sum / n;
}
double dp(int x1, int y1, int x2, int y2, int k)
{
double &v = f[x1][y1][x2][y2][k];//只是用来简写
if (v >= 0) return v;//已经计算过，直接return
if (k == 1) return v = get(x1, y1, x2, y2);//不用切
v = INF;
for (int i = x1; i < x2; i ++ )
{//枚举横切
v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));//对下面继续切
v = min(v, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));//对上面继续切
}
for (int i = y1; i < y2; i ++ )
{
v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
v = min(v, get(x1, i + 1, x2, y2) + dp(x1, y1, x2, i, k - 1));
}
return v;
}
int main()
{
cin >> n;
for (int i = 1; i <= m; i ++ )
for (int j = 1; j <= m; j ++ )
{
cin >> s[i][j];//边输入边得到二维前后缀矩阵
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
X = (double)s[m][m] / n;//平均值
memset(f, -1, sizeof f);//double在计算机中存储是科学记数法，全是1的话表示-NAN
printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n)));
return 0;
}
数位DP
AcWing 1081. 度的数量
/*
数位dp的题目一般会问，某个区间内，满足某种性质的数的个数。
对应的数位dp问题有相应的解题技巧：
利用前缀和，比如求区间[x,y]中的个数，转化成求[0,y]的个数 -[0,x-1]的个数。
利用树的结构来考虑（按位分类讨论）
题目就是在一个区间[x,y]内，有多少个符合题意的数，这里的符合题意是指：这个数的B进制表示中，其中有K位上是1、其他位上全是0。
该类题目的核心就是根据数位进行分类讨论。
第一步，先将数x转化成为B进制，记为N。
第二步，分类讨论。既然每一位上的数都已给定，我们称之为每一位的“限定值”都已给出。比如一个数的B进制表示是456，最高位是4，这一位的“限定值”就是4；
第三位上是6，这一位的“限定值”就是6. 如此说来，每位上可取的数的大小就确定了。每一位都分两种情况：
取限定值；
取 0~限定值-1 中的任一个数。
其实，对应本题，这里每个数的取值可能用不到限定值！！！只有限定值是1的时候才会用到！！！为什么呢？
因为本题求的是K个位上填1，其他位上填0，根本不会出现其他数字，所以当出现3，4，9这样的数字的时候直接break。
对于B进制数N（共n位），从最高位（第n位）开始遍历每1位，对于第 i 位，last表示第i位之前的所有位取过的1的个数。第i位上的数字x有三种情况：
1；当前位为 大于1时：
这位可以取0， 那么就是剩下位中取k-last个1；
这位可以取1， 那么就是剩下位中取k-last-1个1；(但必须大于1的时候才可以取）
2：当这位是1时， 那么代表着一种确定的 B^i ,所以不能动， 但仍可以枚举这位是0的情况；
3：当这位是0时， 这位只能取0， 那么只能看下一位的， 那么就归结到下一位的分类中了， 所以不用讨论；
这里用记忆化搜索来求组合数。存在数组f中，f[i][j]表示 从i个数中选出j个数的组合数。比如f[5][2]表示从5个数中选出2个数
*/
#include <iostream>
#include <vector>
using namespace std;
const int N = 35; //位数
int f[N][N];// f[a][b]表示从a个数中选b个数的方案数，即组合数
int K, B; //K是能用的1的个数，B是B进制
//求组合数：预处理
void init(){
for(int i=0; i< N ;i ++)
for(int j =0; j<= i ;j++)
if(!j) f[i][j] =1;
else f[i][j] =f[i-1][j] +f[i-1][j-1];
}
//求区间[0,n]中的 “满足条件的数” 的个数
//“满足条件的数”是指：一个数的B进制表示，其中有K位是1、其他位全是0
int dp(int n){
if(n == 0) return 0; //如果上界n是0，直接就是0种
vector<int> nums; //存放n在B进制下的每一位
//把n在B进制下的每一位单独拿出来
while(n) nums.push_back( n% B) , n/= B;
int res = 0;//最终答案：[0,n]中共有多少个合法的数
//last在数位dp中存的是：遍历当前位的时候，记录之前那些位已经占用多少个1
int last = 0;
//从最高位开始遍历每一位
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums[i];
if (x == 0) continue;
res += f[i][K - last]; // count 0
if (x == 1){//如果x==1，那么i位取1的时候，还要进行讨论，后面i位不能随便取，也就不是组合数
last++;
if (K == last){
res++;
break;
}
}
else if (x > 1) {//如果x>1，就可以直接用组合数表示出来，不用进行讨论，也就是i位取1的时候，后面i位随便取k-last-1个1
res += f[i][K - last - 1];
break;
}
}
return res;
}
int main(){
init();
int l,r;
cin >> l >> r >> K >>B;
cout<< dp(r) - dp(l-1) <<endl;
}
AcWing 1082. 数字游戏
/*
先求0到n中不降数的个数
按照数位DP分析步骤： 假设我们当前枚举到第i位，且第i位上的数字是x，那么现在对于答案的第i位数字j来说，可以填两类数字：
1.j取0~x-1
DP或排列组合
f[i][j] 表示一共有i位，且最高位数字为j的不降数的个数
状态转移： 因为最高位已经固定，所以假设第i-1位是k，根据不降数定义k>=j,所以
那么res += f[i-1][k];（k=j,j+1,...,9）
2.j取x
last记录x，再枚举下一位
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 15;
int f[N][N];//f[i][j]表示i位数且最高位为j的不降序的方案数
void init()
{
for(int i=0;i<=9;i++) f[1][i]=1;
//初始化,因为只有一位的方案数只有一个
for(int i=2;i<N;i++)
for(int j=0;j<=9;j++)
for(int k=j;k<=9;k++)//状态划分
f[i][j]+=f[i-1][k];
}
int dp(int n)
{
if(!n) return 1;//n=0,只有0这一种方案
//因为当n=0时,下面的while循环无法通过,所以要进行特判
vector<int> num;
while(n) num.push_back(n%10),n/=10;//单独把n的每一位抠出来
int ans=0;
int lt=0;//保存上一位的最大值
for(int i=num.size()-1;i>=0;i--)
{
int x=num[i];
if(lt>x) break;//如果上一位最大值大于x的话,不构成降序,所以右边分支结束
//左边分支,因为要保持不降序,所以j>=lt
for(int j=lt;j<x;j++) ans+=f[i+1][j];//(0~i位，一共有i+1位)
lt=x;//更新，当前这一位放x，后续方案数继续枚举
if(!i) ans++;//全部枚举完了也同样构成一种方案
}
return ans;
}
int main()
{
init();
int l, r;
while (cin >> l >> r) cout << dp(r) - dp(l - 1) << endl;
return 0;
}
AcWing 1083. Windy数
/*
假设我们当前枚举到第i位(设共有n位)，且第i位上的数字为x，那么对于答案中第i位数字j来说，有两类：
1.0~x-1 (如果第i位是最高位，这里是1~x-1以便去除前导0)
我们用last记录上一位的数字，然后枚举j，如果abs(j-last) >= 2 就累加答案，res += f[i+1][j];
2.x
不需要枚举j，last = x,再枚举之后的数位即可
上述做完之后，由于上面的答案都是n位的，对于数位个数低于n的，再累加到答案中就行了
f[i][j] 表示一共有i位，且最高位数字为j的满足windy数定义的数的个数
状态转移： 因为第i位是j已经确定，考虑第i-1位，设第i-1位数字为k，那么根据windy数定义只要abs(k-j) >= 2就可以转移过来
*/
#include <iostream>
#include <vector>
using namespace std;
const int N = 11;//最多10位
int f[N][N]; //f[i][j] 表示一共有i位，且最高为是数字j的满足wingy数定义的数的个数
void init(){
for(int i = 0; i<=9; i++) f[1][i] = 1;//预处理一位数的情况
for(int i = 2; i<=N; i++)
for(int j = 0; j<=9; j++)
for(int k = 0; k<=9; k++)
if(abs(k-j)>=2) f[i][j] += f[i-1][k];
}
int dp(int n){
if (!n) return 0;
vector<int> a;
while(n)a.push_back(n%10),n/=10;
int res = 0,last = -10;
int len = a.size()-1;
//答案是a.size()位的
for(int i =len; i>=0; --i){
int x = a[i];
for(int j = (i==len); j<x; ++j) //最高位从1开始
if(abs(j-last)>=2) res += f[i+1][j];
if(abs(x-last)<2) break; //不满足定义，直接break
else last = x;
if(!i) res ++;
}
//答案小于a.size()位的
for(int i = 1; i<=len; i++)
for(int j = 1; j<=9; j++)//从1开始枚举
res += f[i][j];
return res;
}
int main()
{
init();
int l,r;
cin>>l>>r;
cout<<dp(r)-dp(l-1);
return 0;
}
AcWing 1084. 数字游戏 II
/*
在几道数位Dp题目练习过后，这类题目重点在于找到左边那一类如何直接计算
对于这一题来说，假设我们当前枚举到的第i位，且第i位上的数字是x，那么对于答案中的第i位数字j来说，可以填两类数：
1.0~x-1
我们用last表示到当前为止，前面数位上的数字之和，对此，当前第i位数字为j，前面数字之和为last，那么
后i+1位(包括j这一位)数字之和sum与last的关系就是(last+sum)%N == 0,那么sum%N的结果等价于(-last)%N,
所以res += f[i+1][j][(-last%N)]; (后面会提到f数组的处理)
2.x
如果j填x，那么不用枚举了，last += x，再枚举下一位即可
f数组的处理
f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模N结果为k的数的个数
状态转移： 因为第i位已经是j，且所有数字之和模N为k，所以我们考虑第i-1位，假设第i-1位数字是x，由于j已经知道，
那么剩下的i-1位数字之和模N的结果就是(k-j)%N
*/
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 12, M = 102;
int f[N][10][M]; //f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模p位k的数字个数
int p;
int mod(int u,int v){
return (u%v+v)%v; //c++的%会得到负数，需要做一个偏移
}
void init(){
memset(f,0,sizeof f); //多组测试数据，f数组要清空
for(int i = 0; i<=9; i++) f[1][i][i%p]++;
for(int i = 2; i<N; i++)
for(int j = 0; j<=9; j++)
for(int k = 0; k<p; k++)
for(int x = 0; x<=9; x++)
f[i][j][k] += f[i-1][x][mod(k-j,p)];
}
int dp(int n){
if(!n) return 1;
int res = 0,last = 0;
vector<int> a;
while(n) a.push_back(n%10),n/=10;
int len = a.size()-1;
for(int i = len; i>=0; --i){
int x =a[i];
for(int j = 0; j<x; j++) //第i位放0~x-1
res += f[i+1][j][mod(-last,p)]; //0~i位，所以一共有i+1位
last += x;
if(!i && last % p == 0) res ++; //最后判断最右边的那一个数是否合法
}
return res;
}
int main()
{
int l,r;
while(cin>>l>>r>>p){
init();
cout<<dp(r)-dp(l-1)<<endl;
}
return 0;
}
AcWing 1085. 不要62
/*
数位Dp
还是相同的套路，假设数字num当前枚举到第i位，且第i位数字是x，那么对于答案的第i位来说，假设是j，有两种填法：
1.0~x-1
我们用last表示num中第i位的高一位数字，那么根据题意，j不能是4 且 当last是6的时候j不能为2，这两种情况在枚举的时候特判一下即可
然后，累加到答案中，res += f[i+1][j]
2.x
那么这一位就不用处理了，更新一下last即可，last = x
f数组的处理
f[i][j] 表示一共有i位，且最高位是j的满足新的士牌照定义的数的个数
转态转移： 第i位是j已知，那么考虑第i-1位，假设为k，根据牌照定义，j为6时k不为2且k不能等于4
*/
#include <iostream>
#include <vector>
using namespace std;
const int N = 12;
int f[N][10];
void init(){
for(int i = 0; i<=9; i++) f[1][i] = !(i==4);
for(int i = 2; i<N; i++)
for(int j = 0; j<=9; j++){
if(j == 4) continue;
for(int k = 0; k<=9; k++){
if(k == 4 || (j==6 && k==2)) continue;
f[i][j] += f[i-1][k];
}
}
}
int dp(int n){
if(!n) return 1; //最好特判一下，否则进到下面可能出问题
int res = 0, last = 0; //last表示num高一位的数字是多少
vector<int> a;
while(n) a.push_back(n%10),n/=10;
int len = a.size()-1;
for(int i = len; i>=0; i--){
int x = a[i];
for(int j = 0; j<x; j++){
if(j == 4 || (last == 6 && j == 2)) continue;
res += f[i+1][j];
}
if(x == 4 || (last == 6 && x == 2)) break; //特判一下，不满足题意直接break
last = x;
if(!i) res ++;
}
return res;
}
int main()
{
init();
int l,r;
while(cin>>l>>r,l&&r){
cout<<dp(r)-dp(l-1)<<endl;
}
return 0;
}
