动态规划专练
一.01背包
最值——DP
经典DP分析法:
(1)状态表示
<1>集合f[i,j]:从前i个物品中选,且总体积不超过j的所有选法的集合
<2>属性:max
(2)状态计算:对于每一个物品都有选和不选两种选择
不选:f[i,j] = f[i-1,j]
选:f[i,j] = f[i-1,j-v[i]]+w[i]
取max
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N],v[N],w[N];
int n,V;
int main()
{
scanf("%d %d",&n,&V);
for(int i = 1;i <= n;i ++) scanf("%d %d",&v[i],&w[i]);
for(int i = 1;i <= n;i ++) //必须从1开始,因为要用到f[i-1]这个下标,从0开始会出错
{
for(int j = 0;j <= V;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]);
}
}
printf("%d",f[n][V]);
return 0;
}
优化:用滚动数组优化为一维
f[i,j] = f[i-1,j]; //这里只用到了i和i-1,去掉i
f[i,j]=max(f[i,j],f[i-1,j-v[i]]+w[i]); //不能直接去掉i,因为,f[i-1,j-v[i]]+w[i]这里用到的是第i-1层的,又j>j-v[i],说明计算f[i,j]时,j-v[i]这一项已经被第i层更新了,所以直接去掉会出错
解决办法:从大到小枚举j即可
#include<iostream>
using namespace std;
const int N = 1010;
int f[N],v[N],w[N];
int n,V;
int main()
{
scanf("%d %d",&n,&V);
for(int i = 1;i <= n;i ++) scanf("%d %d",&v[i],&w[i]);
for(int i = 1;i <= n;i ++)
{
for(int j = V;j >= v[i];j --)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d",f[V]);
return 0;
}
二.摘花生
1.分析题目:求最值——DP
2.经典DP分析法:
(1)状态表示
<1>集合f[i,j]:第i行,第j列摘得的花生数量的所有可能的集合
<2>属性:max
(2)状态计算:对于f[i,j],有两种可能
从上方来:f[i,j] = f[i-1,j]+w[i,j]
从左方来:f[i,j] = f[i,j-1]+w[i,j]
取max
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int w[N][N],f[N][N];
int T,r,c;
int main()
{
scanf("%d",&T);
while(T --)
{
scanf("%d %d",&r,&c);
for(int i = 1;i <= r;i ++)
{
for(int j = 1;j <= c;j ++)
{
scanf("%d",&w[i][j]);
}
}
memset(f,0,sizeof f); //记得更新数组
for(int i = 1;i <= r;i ++)
{
for(int j = 1;j <= c;j ++)
{
f[i][j] = max(f[i-1][j],f[i][j-1])+w[i][j];
}
}
printf("%d\n",f[r][c]);
}
return 0;
}
三.最长上升子序列
和蓝桥杯的接龙数列异曲同工
#include<iostream>
using namespace std;
const int N = 1010;
int f[N],a[N];
int n;
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
int ans = 1;
for(int i = 0;i < n;i ++)
{
f[i] = 1;
for(int j = 0;j < i;j ++)
{
if(a[j] < a[i]) f[i] = max(f[i],f[j] + 1);
ans = max(ans,f[i]);
}
}
printf("%d",ans);
return 0;
}
四.地宫取宝
1.“摘花生和最长上升子序列的组合问题”
2.限制条件:1.从左上到右下;2.恰好取k件;3.按严格递增顺序取物品;
f[i,j,k,c]:(i,j)表示坐标、k表示取的件数,c表示最后一件物品取的价值
3.DP经典分析法:
(1)状态表示
<1>集合f[i,j,k,c]:所有从起点走到(i,j),且已经取了k件物品,且最后一件物品的价值是c的合法方案的集合
<2>属性:count
(2)状态计算:
<1>所有最后一步是从上往下走的情况
不取(i,j):f[i-1,j,k,c]
取(i,j):f[i-1,j,k-1,c’]——遍历
<2>所有最后一步是从左往右走的情况
不取(i,j):f[i,j-1,k,c]
取(i,j):f[i,j-1,k,c’]
4.分析边界:(因为要用到i-1,j-1所以下标从1开始)
选第一个数:f[1,1,1,w[1,1]]
不选第一个数:f[1,1,0,-1]
//不选时,价值应该表示为c数据范围之外的,0<=c<=12,所以用-1表示没有价值,又由于c++中数组下标不能为负数,所以可以将c整体+1,将其范围变成1<=c<=13,用0表示没有价值
#include<iostream>
using namespace std;
const int N = 55;
int f[N][N][13][14],w[N][N],MOD = 1000000007;
int n,m,k;
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= n;i ++) //下标从1开始
{
for(int j = 1;j <= m;j ++)
{
scanf("%d",&w[i][j]);
w[i][j] += 1; //将c整体+1
}
}
//边界
f[1][1][1][w[1][1]] = 1;
f[1][1][0][0] = 1;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
for(int u = 0;u <= k;u ++)
{
for(int v = 0;v < 14;v ++)
{
int &val = f[i][j][u][v]; //因为下面代码要反复写f[i,j,u,v],过于麻烦,&在修改val的值时,f也会被修改
//不选的两种方案数
val = (val + f[i-1][j][u][v])%MOD; //边加边mod,防止爆int
val = (val + f[i][j-1][u][v])%MOD;
//要选(i,j),必须满足此刻的v == w[i][j]
//怎么理解?因为f的定义就是,v是最后一件物品的价值,所以此时讨论的是f[i,j]所以这件物品的价值应该等于(i,j)的价值,即w[i,j]
//怎么理解u>0?
//因为u也是枚举的变量,此刻我们已经选择了(i,j),所以u必须要>0,=0不就表示不选数吗
if(v == w[i][j] && u > 0)
{
for(int c = 0;c < v;c ++)
{
val = (val + f[i-1][j][u-1][c])%MOD;
val = (val + f[i][j-1][u-1][c])%MOD;
}
}
}
}
}
}
int res = 0;
//上面的循环只是算出了每个的方案数,总和得遍历一遍
//这里的巧妙之处在于,利用最后一件物品的价值来遍历求和
//因为k是固定要取的件数,(i,j)是固定要到达的终点
for(int i = 1;i < 14;i ++) res = (res + f[n][m][k][i])%MOD;
printf("%d",res);
return 0;
}
五.波动数列
一.分析过程:(无数次感概!!为什么想的出来啊啊啊)
1.设第一项是x,那么 x,x+d1,x+d1+d2,….,x+d1+d2+…+dn-1
即nx+(n-1)d1+(n-1)d2+…+dn-1 = S
为了后续代码好理解一点,又因为d1,dn-1本来就是可以随便取的变量名
so将上式改为:nx+(n-1)dn-1+(n-2)dn-2+…+d1=S
2.分析变量,有两个:
(1)x,x可取左右整数
(2)di,di有两种选择,+a/-b
因为x变量可能的变化太多了,又因为上述式子是关于x的等式,作一下变换,替换掉x
即x={S-[(n-1)dn-1+(n-2)dn-2+….+d1]} / n
3.从这个式子,可以得出:
(1)任何一个满足条件的序列都对应一组d的取值,反之亦然
(2)求原序列的方案数==求一组d的所有合法取值的方案数
4.那么关于d,只须满足两个条件:
(1)d:两种取法,+a / -b
(2)由上式可知,S-[(n-1)dn-1+(n-2)dn-2+….+d1]必须是n的倍数(保证x是整数)
a tip:这个式子,可以得到:S 和 (n-1)dn-1+(n-2)dn-2+….+d1模n的余数相同
分析至此,回到DP的经典分析法:
5.DP:
(1)状态表示
<1>集合f[i,j]:所有只考虑前i项,且当前的总和除以n的余数为j的方案的集合
<2>属性:count数量
(2)状态计算:很明显,可以划分为两块:
<1>最后一项是a的所有方案
这些方案是:
d1,d2,….di=+a
d1,d2,….di=+a
剔除掉共同项di=+a,前面的部分表示的意思是:
只考虑前i-1项,设总和为C,那么C 和 j – i * a 模n的余数相等
根据集合的定义:前面的部分表示为:f[i-1,j-i*a%n]
<2>最后一项是b的所有方案
同理,这一部分:f[i-1,j+i*b%n]
既然是求count,两者相加即可
#include<iostream>
using namespace std;
const int N = 1010,MOD = 100000007;
int f[N][N];
int n,s,a,b;
int get_mod(int a,int b) //因为j-i*a..可能为负数,负数mod n会得到负数,而下标不能为负数
{
return (a % b + b) % b; //将负数转为正数
}
int main()
{
scanf("%d %d %d %d",&n,&s,&a,&b);
f[0][0] = 1; //边界:什么都不选,为1
for(int i = 1;i < n;i ++) //因为要用到下标j-1,所以从1开始,且循环到n-1
{
for(int j = 0;j < n;j ++) //j表示的含义是%n的余数,所以范围从0到n
{
f[i][j] = (f[i-1][get_mod(j-i*a,n)]+f[i-1][get_mod(j+i*b,n)])%MOD;
}
}
printf("%d",f[n-1][get_mod(s,n)]%MOD);
return 0;
}
版权声明:本文为博主作者:ada7_原创文章,版权归属原作者,如果侵权,请联系我们删除!