bzoj3191卡牌游戏
2024-09-01 22:57:18
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3191
原本想模拟过程,从t个人推到1个人;
但是怎么转移呢?想状压,可是50位压不到角标里。
那就随便转移吧,把当前人的生存方案数加给所有有可能成为下一轮中自己的人。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=;
int n,m,a[N];
ll dp[N][N],sum;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d",&a[i]);
dp[n][]=;
for(int t=n;t>;t--)
for(int i=;i<=n;i++)
if(dp[t][i])
{
// printf("t=%d i=%d dp=%d\n",t,i,dp[t][i]);
for(int j=;j<=m;j++)
{
int c=a[j]%t,l=i+c+,r=i-(t-c-);
// printf("i=%d aj=%d l=%d r=%d\n",i,a[j],l,r);
if(l>r)for(int k=;k<=n;k++)if(k>=r||k<=l)dp[t-][k]+=dp[t][i];
else for(int k=l;k<=r;k++)
dp[t-][k]+=dp[t][i];
}
}
for(int i=;i<=n;i++)sum+=dp[][i];
for(int i=;i<=n;i++)
printf("%.2lf",(double)dp[][i]*/(double)sum),cout<<"% ";
return ;
}
这当然是不对的。那个“有可能成为下一轮中自己的人”不能保证就是下一轮中的自己。
那怎么办?看看TJ,发现大家是用相对编号来记录下一轮中的自己是哪个人的。
用记忆化搜索可以想得更灵活一点。以后尝试用这个角度思考。不然自己容易想不出来……
概率不用每一步都算好。可以之前一直算的是方案数,最后再换算成概率。有时候这样比较方便。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
int n,m,a[N];
bool vis[N][N];
double dp[N][N],sum;
double sol(int i,int j)
{
if(vis[i][j])return dp[i][j];vis[i][j]=;
if(i==)return dp[i][j]=;
for(int k=;k<=m;k++)
if(a[k]%i!=j%i)//j%i,不是j (j==i)
dp[i][j]+=sol(i-,(j-(a[k]%i)+i)%i);
// dp[i][j]/=m;
return dp[i][j];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)sum+=sol(n,i);
for(int i=;i<=n;i++)
{
printf("%.2lf%%",sol(n,i)/sum*);
if(i!=n)printf(" ");
}
return ;
}
最新文章
- position:fixed 属性在iphone 中不起作用
- mybatis 特殊符号及like的使用
- [地图SkyLine二次开发]框架(1)
- 遇到bug怎么办
- 【Cocos2d-x 3.x】 调度器Scheduler类源码分析
- Python自动化 【第十二篇】:Python进阶-MySQL和ORM
- Effective C++ -----条款06:若不想使用编译器自动生成的函数,就该明确拒绝
- Style file: generic.xaml
- 用Ogre实现《天龙八部》场景中水面(TerrainLiquid)详解
- 50道经典的JAVA编程题 (1-5)
- Python学习入门基础教程(learning Python)--6.4 Python的list与函数
- 结构-行为-样式-Css笔记
- iOS UIScrollview代理方法
- 日常API之百度翻译
- Unreal Engine 4(虚幻UE4)GameplayAbilities 插件入门教程(三)技能标签(Ability Tags)
- Android App版本自动更新
- Qt坑点汇总
- Java爬取网络博客文章
- Android应用系列:完美运行GIF格式的ImageView(附源码)
- mysql索引简单分析
热门文章
- SQL学习笔记五之MySQL索引原理与慢查询优化
- bzoj1628 [Usaco2007 Demo]City skyline(单调栈)
- Linux内核分析 05
- 20135302魏静静——Linux课程期中总结
- ubuntu18.04 install pip
- System.DateTimeKind 的用法
- Codeforces Round #396 (Div. 2) A,B,C,D,E
- Android-----购物车(包含侧滑删除,商品筛选,商品增加和减少,价格计算,店铺分类等)
- linux下运行jar
- HDU 2612 Find a way bfs 难度:1