好题
一开始想状压 但是转移根本无从下手
设f[i][j]表示i~j天的最低成本 可以想到从第i天到第j天要么不换方案，要么从第k天换一种方案，类似于floyd求最短路
就是 f[i][j]=min(f[i][j],f[i][p]+f[p+1][j]+k) 这是个区间dp
然后我们发现 对于题目中有些”不可用“的点 只需在跑spfa的时候特判一下就阔以了
然后spfa预处理出f数组
#include<bits/stdc++.h> #define N 105 #define M 25 #define INF 0x3f3f3f3f #define E 100005 using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } struct Node { int to,next,val; }edge[2*E]; int n,m,k,e,first[M],tot,d,dis[M],f[N][N]; //f[i][j]:第i天到第j天的总成本 bool able[M][N],inque[M]; inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } inline bool isable(int node,int from,int to) { for(int i=from;i<=to;i++) if(!able[node][i]) return false; return true; } inline int spfa(int from,int to) { memset(inque,false,sizeof(inque)); memset(dis,0x3f,sizeof(dis)); queue <int> q; q.push(1); inque[1]=true; dis[1]=0; while(!q.empty()) { int now=q.front(); q.pop(); inque[now]=false; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(isable(vis,from,to)&&dis[vis]>dis[now]+edge[u].val) { dis[vis]=dis[now]+edge[u].val; if(!inque[vis]) { q.push(vis); inque[vis]=true; } } } } return dis[m]==INF?INF:dis[m]*(to-from+1); } int main() { read(n); read(m); read(k); read(e); for(int i=1,x,y,z;i<=e;i++) { read(x); read(y); read(z); addedge(x,y,z); addedge(y,x,z); } read(d); memset(able,true,sizeof(able)); for(int i=1,p,x,y;i<=d;i++) { read(p); read(x); read(y); for(int j=x;j<=y;j++) able[p][j]=false; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=spfa(i,j); for(int len=2;len<=n;len++) { for(int st=1;st+len-1<=n;st++) { const int ed=st+len-1; for(int p=st;p<ed;p++) { f[st][ed]=min(f[st][ed],f[st][p]+f[p+1][ed]+k); } } } cout<<f[1][n]; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9847916.html
