錯是被學(xué)長挑出來的。。。QWQ@Monster_Yi

f[i][j][0/1] 為 第i天，換j次，換1/沒換0

然后大力DP

#include<cstdio> #include<iostream> #include<cstring> #define R register int using namespace std; struct node{int c,d;#define c(i) a[i].c#define d(i) a[i].d }a[10010]; int n,m,v,ee; long long e[310][310]; double k[2010],f[2010][2010][2],ans=1e17+10; inline void floyed() {for(R k=1;k<=v;++k) for(R i=1;i<=v;++i) for(R j=1;j<=v;++j) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);} signed main() {scanf("%d%d%d%d",&n,&m,&v,&ee);for(R i=1;i<=n;++i) scanf("%d",&c(i)); for(R i=1;i<=n;++i) scanf("%d",&d(i)); for(R i=1;i<=n;++i) scanf("%lf",&k[i]);memset(e,0x3f,sizeof e); for(R i=1,u,vv,w;i<=ee;++i) scanf("%d%d%d",&u,&vv,&w),e[u][vv]=e[vv][u]=min(e[u][vv],(long long)w);for(R i=1;i<=v;++i) e[i][i]=0; floyed(); //for(R i=1;i<=v;++i,cout<<endl)for(R j=1;j<=v;++j) cout<<e[i][j]<<" ";for(R i=0;i<=n;++i) for(R j=0;j<=n;++j) f[i][j][1]=f[i][j][0]=1e17+10; f[1][0][0]=f[1][1][1]=0;for(R i=2;i<=n;++i) { f[i][0][0]=f[i-1][0][0]+e[c(i)][c(i-1)];for(R j=1;j<=min(i,m);++j){f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+e[c(i)][c(i-1)],f[i-1][j][1]+k[i-1]*e[c(i)][d(i-1)]+(1-k[i-1])*e[c(i)][c(i-1)]));f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][0]+k[i]*e[d(i)][c(i-1)]+(1-k[i])*e[c(i)][c(i-1)],f[i-1][j-1][1]+k[i-1]*k[i]*e[d(i)][d(i-1)]+(1-k[i])*(1-k[i-1])*e[c(i)][c(i-1)]+k[i]*(1-k[i-1])*e[d(i)][c(i-1)]+(1-k[i])*k[i-1]*e[c(i)][d(i-1)]));}} for(R i=0;i<=m;++i) ans=min(min(f[n][i][0],f[n][i][1]),ans);//,cout<<f[n][i][0]<<" "<<f[n][i][1]<<endl;printf("%.2lf\n",ans); }

---

2019.04.07

轉(zhuǎn)載于:https://www.cnblogs.com/Jackpei/p/10665482.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4720: [Noip2016]换教室的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。