NOIP2016换教室

题目传送门
md考场上xjb写完了暴力还™写错了,据说暴力分共76分啊,我却只有20分。

不管了tmd
设$f[i][j][1/0]$表示前i节课,申请了j次,这一次申请/不申请的总耗费体力值期望的最小值。
显然对于这一次,申请/不申请,有两种情况,就是上一次申请和上一次不申请。
状态转移方程暴力推就好,注意这一次和上一次申请通过和不通过是两种情况。
也就是从哪个教室到哪个教室都不确定的,体力花费值根据期望的定义算。
算了直接放代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
Author: CNYALI_LK
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define endl '\n'
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
struct inout{
// 输入输出略。
};
inout io;
int c[2333],d[2333];
double f[2333][2333][2],k[2333];
int a[345][345];
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
io.init();
int n,m,v,e,u,wea,w;
io>>n>>m>>v>>e;
up(i,1,n){
io>>c[i];
}
up(i,1,n)io>>d[i];
up(i,1,n)io>>k[i];
up(i,1,v)up(j,i+1,v)a[i][j]=a[j][i]=0x3f3f3f3f;
up(i,1,e){
io>>u>>wea>>w;
chkmin(a[u][wea],w);
chkmin(a[wea][u],w);
}
up(k,1,v)up(i,1,v)up(j,1,v)chkmin(a[i][j],a[i][k]+a[k][j]);
//注意是v个教室!v个教室!v个教室!!!!!!!

up(i,1,m)f[0][i][0]=f[0][i][1]=0;
up(i,1,n){
f[i][0][0]=f[i-1][0][0]+a[c[i-1]][c[i]];
f[i][0][1]=1e10;
up(j,1,m){
f[i][j][0]=min(f[i-1][j][0]+a[c[i]][c[i-1]],f[i-1][j][1]+k[i-1]*a[d[i-1]][c[i]]+(1-k[i-1])*a[c[i-1]][c[i]]);//暴力转移
f[i][j][1]=min(
f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]],
f[i-1][j-1][1]+k[i]*k[i-1]*a[d[i-1]][d[i]]+
(1-k[i])*k[i-1]*a[d[i-1]][c[i]]+k[i]*(1-k[i-1])*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]]
);//更暴力的转移
}
}
double ans=1e9;
up(i,0,m){
chkmin(ans,f[n][i][1]);
chkmin(ans,f[n][i][0]);
}
printf("%.2lf\n",ans);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×