bzoj1867: [Noi1999]钉子和小球(DP)
2024-09-02 04:55:16
一眼题...输出分数格式才是这题的难点QAQ
学习了分数结构体...
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=,inf=1e9;
struct fra{ll u,d;fra(ll a=,ll b=){u=a,d=b;}}f[maxn][maxn];
int n,m;
bool mp[maxn][maxn];
int readch()
{
char ch=getchar();
while(ch==' '||ch=='\n'||ch=='\t'||ch=='\r')ch=getchar();
return ch=='*';
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void sim(fra &x){ll t=gcd(x.u,x.d);x.u/=t;x.d/=t;}
fra operator+(fra x,fra y)
{
ll t=gcd(x.d,y.d);
fra c=fra(y.d/t*x.u+x.d/t*y.u,x.d/t*y.d);
return sim(c),c;
}
fra operator*(fra x,fra y)
{
fra c=fra(x.u*y.u,x.d*y.d);
return sim(c),c;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
mp[i][j]=readch();
f[][]=fra(,);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
if(mp[i][j])f[i+][j]=f[i+][j]+f[i][j]*fra(,),f[i+][j+]=f[i+][j+]+f[i][j]*fra(,);
else f[i+][j+]=f[i+][j+]+f[i][j];
printf("%lld/%lld",f[n+][m+].u,f[n+][m+].d);
return ;
}
最新文章
- 浅谈UDP(数据包长度,收包能力,丢包及进程结构选择)
- composer 安装
- PhpSms 稳定可靠的php短信发送库
- (转)原始图像数据和PDF中的图像数据
- go语言指针符号的*和&;
- 支持多种浏览器的纯css下拉菜单
- C++-copy constructor、copy-assignment operator、destructor
- UI1_UIScrollView
- mybatis传入map参数parameterType
- iOS 项目中将 http 改成 https 后需要改动的地方(密钥验证)
- 关于在SLES11, RHEL6, OEL6 and UEK2 Kernels使用hugepages的告警
- VHDL TestBench 测试终止时自动结束仿真——assert方法
- C#操作WORD换行
- maven项目引入sqljdbc4 找不到包的完美 解决方案。
- Java之Collections.emptyList()、emptySet()、emptyMap()的作用和好处以及要注意的地方
- 【HDFS API编程】删除文件
- Python框架学习之用Flask创建一个简单项目
- Angular4学习笔记-目录汇总
- 《C#从现象到本质》读书笔记(三)第3章C#类型基础(下)
- npm run build 打包后,如何运行在本地查看效果(Apache服务)