DP各种题之三
DP各种题之三
P2719搞笑世界杯
P1694 [mc生存] 卖东西
P1832 A+B Problem [再升级]
P2362围栏木桩
P2008大朋友的游戏
搞笑世界杯（过河卒既视感？）
因为是抛硬币决定买哪种票
所以前面的人买AB两种票的几率都相同，为0.5
难设计状态为 f [ i ] [ j ]表示买 i 张 A 类票
j 张 B 类票时队伍最后两个人买到同一类型球票的概率
可得转移方程
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
f[i][j]=(f[i-1][j]+f[i][j-1])*0.5;需要注意的是初始化
只买 i （i 不等于 1） 张 A 票或只买 i 张 B 票
买到同一类型球票的概率都为1
而 f [ 1 ] [ 0 ] f [ 0 ] [ 1 ] 则表示只买一张球票
应该初始化为0
for(register int i=2;i<=n;i++) f[i][0]=f[0][i]=1;最后输出答案即可
printf("%.4f",f[n][n]);[mc生存] 卖东西
其实可以贪心+排序做
当然也可以多重背包
其实难点就是把名字对应起来
开两个map就行
一个把名字设为key
输入时进行合并
另一个把名字设为value
把序号设为 key
用序号检索名字
再用名字检索 ai ， bi ， ci
map <string,things> t;
map <int,string> name;多重背包:
（做法来自 @suuuuy 神仙）
设 f [ i ] [ j ] 表示第 i 件物品剩余 j 个格子所能达到的最大价值
for(register int i=1;i<=cnt;i++) // 枚举物品
for(register int j=0;j<=m;j++) // 枚举格子数-> 容量
for(register int k=0;k<=min(j*c[i],a[i]);k++) // 枚举放几个物品
f[i][j]=min(f[i-1][j],f[i-1][j-ceil((double)k/c[i])]+k*b[i]);其中
j-ceil((double)k/c[i])表示放当前物品（数量为k）剩余的格子数
j就是多重背包中的容量
k就是多重背包中物品的数量
A+B Problem [再升级]
类似完全背包
只需要改为方案数即可
f_prime();
f[0]=1;
for(register int i=1;i<=l;i++) // 物品
for(register int j=prime[i];j<=n;j++) // 容量
f[j]+=f[j-prime[i]];
printf("%lld",f[n]);围栏木桩
我不会告诉你我想了一个小时然后看了题解才会的
真·懵的一匹
主要思想就是
设 g [ i ] 为以 i 结尾的最长上升子序列方案数
f [ i ] 还是以 i 结尾的最长上升子序列的长度
f [ i ] 的状态转移是与 g [ i ] 相关的
当能够更新 f [ i ] 时
显然此时以 i 结尾的最长上升子序列改变了
因此以 i 结尾的最长上升子序列方案数也改变了
g [ i ] 更新为 g [ j ]
而如果此时发现以 j 结尾的最长上升子序列长度+1与以 i 结尾的最长上升子序列长度相同
显然找到了另外的可能方案
g [ i ] 加上 g [ j ]
代码
for(register int i=1;i<=n;i++) f[i]=1,g[i]=1;
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(register int j=1;j<i;j++)
{
if(a[i]<a[j]) continue;
if(f[i]<f[j]+1) f[i]=f[j]+1,g[i]=g[j];
else if(f[i]==f[j]+1) g[i]+=g[j];
}
}
int ans1=0,ans2=0;
for(register int i=1;i<=n;i++)
if(ans1<f[i]) ans2=g[i],ans1=f[i];
printf("%d %d\n",ans1,ans2);大朋友的游戏
这个题其实状态设计跟围栏木桩相似
设 g [ i ] 表示以 i 结尾的最长不下降子序列中所有数之和
f [ i ] 还是以 i 结尾的最长上升子序列的长度
易知 f [ i ] 的状态转移是与 g [ i ] 相关的
当能够更新 f [ i ] 时
显然此时以 i 结尾的最长上升子序列改变了
因此以 i 结尾的最长上升子序列方案数也改变了
g [ i ] 更新为 g [ j ] + a [ i ]
题目中还要求编号字典序最小
那么当我们转移到 f [ i ] = = f [ j ] + 1 时
就不再更新 g 数组
这样 g 数组一定是被字典序最小的最长上升子序列转移过来的
代码
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<i;j++)
{
if(a[i]<a[j]) continue;
if(f[i]<f[j]+1) f[i]=f[j]+1,g[i]=g[j]+a[i];
}
}