题解

34 条题解

  • 4
    @ 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
    @ 2013-12-21 23:18:26

    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
    @ 2013-05-26 19:25:36

    1次AC~
    i表示天,f[i]表状态,转移很简单了
    至于每次的决策j,算一遍SSSP(j到i有限制的港口不能走)
    怎么搞都能A,本人BellmanFold....
    小优化:决策j从i倒着枚举,若某个j使得1到m不连通了,就可以break了。。。

  • 0
    @ 2012-10-15 10:53:49

    额,几天前考试刚考了这道题,想了半上午,感觉挺好的这题。

    SPFA预处理+区间DP 想到区间DP就行,想做的同学仔细想一下怎么预处理

  • 0
    @ 2012-07-16 16:34:20

    晕,找不到最短路的返回值返回的小一点好了,我1

  • 0
    @ 2010-03-18 23:01:24

    看M那么小,而且还是 N*2^(M-2),直接状态压缩DP,结果后三个点TL。。。

  • 0
    @ 2009-11-01 16:27:25

    水题

  • 0
    @ 2009-11-01 16:22:43

    fillchar真不好用,老是wrong215

    第一次做这种题目,这种方法真牛,,

    我DP真该加强了..

  • 0
    @ 2009-11-01 14:20:07

    两零一步报错的,大家注意下

  • 0
    @ 2009-10-29 23:10:34

    已经有牛人给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
    @ 2009-10-28 10:00:31

    把天数看成了20,悲剧

  • 0
    @ 2009-09-17 17:19:07

    题目有些含糊不清。看懂题目写出方程就成了难度1.

  • 0
    @ 2009-09-14 19:42:37
  • 0
    @ 2009-09-05 08:28:11

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    SPFA最后忘记弹出队列了...WA五个点N次..郁闷..

  • 0
    @ 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 有效耗时:0ms

    N,M搞错 害我WA了半个小时 Orz

  • 0
    @ 2009-09-04 15:50:04

    编译通过...

    ├ 测试数据 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
    @ 2009-08-19 17:39:34

    原来的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

信息

ID
1173
难度
5
分类
动态规划 点击显示
标签
递交数
744
已通过
277
通过率
37%
被复制
4
上传者