34 条题解
-
4
PowderHan LV 10 @ 2017-05-08 12:34:31
/* 好题好题~ 看到这道题原型是很容易想到划分型dp的 即我们定义f[i]表示到第i天需要的最小代价 很容易发现是具有最优子结构和无后效性性质的 那么很容易得到这样一个转移方程式 f[i]=min(f[j],f[j]+cost[j+1][i]+k) 其中cost[i][j]表示如果[i,j]这个天数段都一直走同一个路线所需要的最小代价 如果无法做到就是INF 即枚举上一个j改变路线过来 关键是这个cost[][]怎么处理惹 我们可以用最短路来做了 对于读入的不能运输的条件我们只需要用一个数组 nocan[k][t]表示第t天k码头不能运输 那么就可以直接记录下 然后用SPFA跑最短路 即跑一边[t1,t2]这个时间内的最短路 (如果t1到t2都走同一条路的话) 如果有一个是跑不到的就返回INF 我们只需要每次在扩展的时候都只扩展在[t1,t2]都可以运输的点 然后就可以预处理出整个cost[][] 时间就是O(t^2km) dp的时间是O(t^2) 这里加入一个优化 j从后向前枚举 如果有一个cost[j][i]不能成立了 那么必然cost[j-1][i]也不能成立~ 这样就可以直接break 但实际因为t很小了威力不是很大~ 好题~涨姿势惹 dp和最短路的结合~！ */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int MAXN=22; const int MAXT=105; const int MAXM=450; const int INF=(1<<28)-1; struct Edge { int to,w,next; }e[MAXM<<1]; int fisrt[MAXN]; bool nocan[MAXN][MAXT]; bool in[MAXN]; int cost[MAXT][MAXT]; int d[MAXN]; int f[MAXT]; int t,n,m,k; int st,tt; int tot; inline void Add_Edge(int& x,int& y,int& w) { e[++tot].to=y; e[tot].w=w; e[tot].next=fisrt[x]; fisrt[x]=tot; } void init() { int x,y,w,p; memset(fisrt,-1,sizeof(fisrt)); scanf("%d%d%d%d",&t,&n,&k,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); Add_Edge(x,y,w); Add_Edge(y,x,w); } int d; scanf("%d",&d); for(int i=1;i<=d;i++) { scanf("%d%d%d",&p,&x,&y); for(int j=x;j<=y;j++) nocan[p][j]=1; } } bool judge(int p) { for(int i=st;i<=tt;i++) if(nocan[p][i]) return 0; return 1; } int SPFA(int x,int y) { st=x; tt=y; if(!judge(1)) return INF; queue<int> q; for(int i=1;i<=n;i++) d[i]=INF; d[1]=0; in[1]=1; q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); in[u]=0; for(int i=fisrt[u];i!=-1;i=e[i].next) { int& v=e[i].to; int& w=e[i].w; if(!judge(v)) continue; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!in[v]) { in[v]=1; q.push(v); } } } } if(d[n]==INF) return INF; else return d[n]*(y-x+1); } void work() { for(int i=1;i<=t;i++) for(int j=i;j<=t;j++) cost[i][j]=SPFA(i,j); f[0]=0; for(int i=1;i<=t;i++) f[i]=cost[1][i]; for(int i=2;i<=t;i++) for(int j=i-1;j>=1;j--) if(cost[j+1][i]!=INF) f[i]=min(f[i],f[j]+cost[j+1][i]+k); else break; cout<<f[t]<<endl; } int main() { init(); work(); return 0; } -
0
-
0
-
0
-
0
dp水秒：
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 460 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 460 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 464 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 476 KiB, score = 10
Accepted, time = 0 ms, mem = 476 KiB, score = 100//*******************************Code********************************************************
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>using namespace std ;
#define MAXN 110
#define MAXM 30
#define inf ( 1 << 20 )int n , m ;
struct graph {
struct edge {
edge *next ;
int t , d ;
} *head[ MAXM ] ;graph ( ) {
memset( head , 0 , sizeof( head ) ) ;
}void Add( int s ,int t ,int d ) {
edge *p = new( edge ) ;
p -> t = t , p -> d = d , p -> next = head[ s ] ;
head[ s ] = p ;
}
void AddEdge( int s , int t , int d ) {
Add( s , t , d ) , Add( t , s , d ) ;
}bool flag[ MAXM ] , f[ MAXM ] , va[ MAXM ][ MAXN ] ;
int dist[ MAXM ] ;
deque< int > Q ;int spfa( ) {
for ( int i = 0 ; i ++ < m ; ) f[ i ] = false , dist[ i ] = inf ;
long long sum = 0 ; Q.clear( ) ;
dist[ 1 ] = 0 , f[ 1 ] = true , Q.push_back( 1 ) ;
while ( ! Q.empty( ) ) {
while ( dist[ Q.front( ) ] > sum / Q.size( ) + 1 ) Q.push_back( Q.front( ) ) , Q.pop_front( ) ;
int v = Q.front( ) ; Q.pop_front( ) ;
f[ v ] = false , sum -= dist[ v ] ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( flag[ p -> t ] && dist[ p -> t ] > dist[ v ] + p -> d ) {
if ( f[ p -> t ] ) sum -= dist[ p -> t ] ;
sum += ( dist[ p -> t ] = dist[ v ] + p -> d ) ;
if ( ! f[ p -> t ] ) {
f[ p -> t ] = true ;
if ( Q.empty( ) ) Q.push_back( p -> t ) ; else if ( dist[ p -> t ] < dist[ Q.front( ) ] ) Q.push_front( p -> t ) ; else Q.push_back( p -> t ) ;
}
}
}
return dist[ m ] ;
}int cost( int l , int r ) {
memset( flag , true , sizeof( flag ) ) ;
for ( int i = 0 ; i ++ < m ; ) for ( int j = l ; j <= r ; j ++ ) if ( ! va[ i ][ j ] ) {
flag[ i ] = false ; break ;
}
return spfa( ) ;
}
} g ;int dp[ MAXN ] , k , e , d ;
int main( ) {
memset( g.va , true , sizeof( g.va ) ) ;
scanf( "%d%d%d%d" , &n , &m , &k , &e ) ;
while ( e -- ) {
int s , t , v ;
scanf( "%d%d%d" , &s , &t , &v ) ;
g.AddEdge( s , t , v ) ;
}
scanf( "%d" , &d ) ;
while ( d -- ) {
int p , a , b;
scanf( "%d%d%d" , &p , &a , &b ) ;
for ( int i = a ; i <= b ; i ++ ) g.va[ p ][ i ] = false ;
}
for ( int i = 0 ; i ++ < n ; ) {
dp[ i ] = g.cost( 1 , i ) * i ;
for ( int j = 0 ; j ++ < i - 1 ; ) dp[ i ] = min( dp[ i ] , dp[ j ] + g.cost( j + 1 , i )*( i - j ) + k ) ;
}
printf( "%d\n" , dp[ n ] ) ;
return 0 ;
} -
0
silence_sure LV 8 @ 2012-10-15 10:53:49
额，几天前考试刚考了这道题，想了半上午，感觉挺好的这题。
SPFA预处理+区间DP 想到区间DP就行，想做的同学仔细想一下怎么预处理 -
0
已经有牛人给DP方程了
f[i]:=min(f[j-1]+min_path(j,i)*(i-j+1)+k,min_path(1,i)*i)多次求最短路min_path(j,i)
只要spfa或者dijstra加上一个判断条件，判断j~i整个时间段里该点的可行性~需要注意的是：
虽然“任何时间都存在至少一条从码头A到码头B的运输路线”
但有的一段时间，（注意是一段），是不存在路线的，这时候求出来的是一开始赋的最大值，再乘一下天数就可能超过longint变成负数了，你再min一下就不对了，所以要判断j~i是否有路径可达才可以转移。 -
0
whyvine的解题报告:
http://blog.sina.com.cn/s/blog_618b6ea70100ew4h.html -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msSPFA最后忘记弹出队列了...WA五个点N次..郁闷..
-
0
yzl609271536 LV 10 @ 2009-09-04 18:49:15
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msN,M搞错 害我WA了半个小时 Orz
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
我晕......
SPFA+DP
把天数看成了20,结果f数组只开了【0..20】......竟然能过9个点...... -
0
原来的10分。。是画蛇添足 加了一个错误优化。。dijkstra都忘记怎么编了。。
失败！编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
PowderHan
LV 10
@ 2017-05-08 12:34:31
