柚子快报邀请码778899分享：算法 动态规划专练
动态规划专练
一.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
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
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
#include
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
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
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
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;
}
柚子快报邀请码778899分享：算法 动态规划专练
推荐阅读
发表评论