NOIP 2016 换教室(期望dp)
2024-08-23 00:50:58
第一次做期望dp
并不知道每个阶段的期望之和就是整个的期望之和
所以一直卡在这
期望=代价*概率
然后注意只有申请了才算期望,否则按原来的。
这道题和前几个课程,申请的限制,当前选或不选,有关
这样很容易写出dp的状态
其实你如果打80分的暴力,会发现把那个暴力记忆化一下
就变成dp,就可以拿满分了,
做题的时候一定要搞清楚每个变量的意义是啥
自己没搞清楚导致数组开小WA两个点
在我的代码中,我在很努力的简化代码了(define)
#include<bits/stdc++.h>
#define down(a, b) a = min(a, b)
#define d(u, v) a[c[i-1][u]][c[i][v]]
#define val(u, v) d(u, v) * (!u ? (1 - k[i-1]) : k[i-1]) * (!v ? (1 - k[i]) : k[i])
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std; const int MAXN = 2e3 + ;
const int MAXM = + ;
double k[MAXN], dp[MAXN][MAXN][];
int a[MAXM][MAXM], n, m, v, e;
int c[MAXN][]; int main()
{
scanf("%d%d%d%d", &n, &m, &v, &e);
_for(i, , n) scanf("%d", &c[i][]);
_for(i, , n) scanf("%d", &c[i][]);
_for(i, , n) scanf("%lf", &k[i]); memset(a, 0x3f, sizeof(a));
_for(i, , v) a[i][i] = ;
_for(i, , e)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
a[u][v] = a[v][u] = min(a[u][v], w);
} _for(K, , v)
_for(i, , v)
_for(j, , v)
a[i][j] = min(a[i][j], a[i][K] + a[K][j]); memset(dp, 0x43, sizeof(dp));
dp[][][] = dp[][][] = ;
_for(i, , n)
_for(j, , m)
{
down(dp[i][j][], dp[i-][j][] + d(, ));
down(dp[i][j][], dp[i-][j][] + d(, ) * k[i-] + d(, ) * ( - k[i-]));
if(j) down(dp[i][j][], dp[i-][j-][] + d(, ) * k[i] + d(, ) * ( - k[i]));
if(j) down(dp[i][j][], dp[i-][j-][] + val(, ) + val(, ) + val(, ) + val(, ));
} double ans = 1e17;
_for(i, , m) down(ans, min(dp[n][i][], dp[n][i][]));
printf("%.2lf\n", ans); return ;
}
最新文章
- JQuery基本知识框架思维导图(上)
- devenv.exe assert failure
- js zTree的用法
- Python实时获取贴吧邮箱名单并向其发送邮件
- CSS魔法堂:你真的理解z-index吗?
- Ubuntu 16.04 下安装Firefox的Flash插件
- DSP中常用的C语言关键字
- Rem &; Viewport
- Break the Chocolate(规律)
- Java引用详解
- VM VirtrualBox 安装centos6.5后的网络设置
- redis五种数据类型
- Python面向对象编程(三)
- restful framework 认证源码流程
- 【MySQL】MySQL零碎积累
- leetCode之旅(5)-博弈论中极为经典的尼姆游戏
- 实现ssr服务端渲染
- SQLServer之创建存储过程
- Java内存模型(JSR133)问与答
- 《JAVA与模式》之状态模式
热门文章
- ubuntu中eclipse无法识别android手机问题
- 安装 KB2844286 导致SharePoint 2010 XSLT web part 显示出现错误
- 最小堆min_stack
- extjs_07_combobox&;amp;tree&;amp;chart
- HDU 4259(Double Dealing-lcm(x1..xn)=lcm(x1,lcm(x2..xn))
- CAS 4.0 配置开发手冊
- Java 获取随机日期
- oc35--自定义构造方法
- wox 快速搜索程序
- (Go)07.Go语言中strings和strconv包示例代码详解02