Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

hawk大大,请帮我看一下吧，submit到吐血了，改到几乎和AC的一模一样了，谢谢！

Posted by sunmoonstar_love at 2005-07-10 23:31:29 on Problem 2465
In Reply To:dp方程是不是：f[i][j] = min{f[i-1][k]+(j+sta[i]-station[i-1]-k)*price[i-1])},对k枚举？另外，这题是单case么？ Posted by:sunmoonstar_love at 2005-07-10 19:47:39

//#include <stdio.h>
#include<iostream>
//#include<fstream>
using namespace std;
int f[102][201],i,j,k,d,dis[102],sta[102],pri[102],n,inf = 1000000000,tmp;

int main()
{
 //   freopen("in.txt","r",stdin); 
 //   freopen("out2.txt","w",stdout);
//    scanf("%d",&d);
//    ifstream cin("in.txt");
//    ofstream cout("out2.txt");
    cin>>d;
    n = 1;  
    while(cin>>sta[n]>>pri[n])   
        n++;
    sta[n] = d;
    sta[0] = 0;
    for(i=1; i<=n; i++)
    {
        dis[i]=sta[i]-sta[i-1];
        if(dis[i]>200 || (i==1||i==n)&&dis[i]>100)
        {
            cout<<"Impossible"<<endl;
            return 0;
        }    
        for(j=0; j<=200; j++)
        {
            f[i][j] = inf;
        }    
    }    
    f[1][100-sta[1]] = 0;
    for(i=1; i<n; i++)
    {
        for(j=0; j<=200; j++)
        {
            if(f[i][j]!=inf)
            {
                for(k=0; k<=200-j; k++)
                {
                    if(j+k>=dis[i+1] && f[i][j]+k*pri[i]<f[i+1][j+k-dis[i+1]])
                    {
                        f[i+1][j+k-dis[i+1]] = f[i][j]+k*pri[i];
                    }    
                }    
            }    
        }    
    }
    cout<<f[n][100]<<endl;    
  //  printf("%d\n",f[n][100]);
 //   cin.close();
 //   cout.close();     
 //   fclose(stdin); 
 //   fclose(stdout);   
    return 0;
}

Followed by:

感觉方程好像不是这样的呢 (1511) frkstyc 2005-07-10 23:33:18
- 方程是对的,我用下面的代码AC了 (1511) xfxyjwf 2005-07-11 00:16:02
  - 立方也能过啊，我还想了平方的 (1633) frkstyc 2005-07-11 00:18:14
    - 大概数据不很强吧 (0) xfxyjwf 2005-07-11 00:20:13
    - 能教教我，平方的么，现在写DP都只会立方的 (0) sunmoonstar_love 2005-07-11 00:41:04
      - 就是p[n][i]=min(p[n-1][i+d],p[n][i-1])+f啊，d是前后两站的距离，f是钱，然后滚动数组就行了 (0) frkstyc 2005-07-11 00:43:54
        原来高手都用滚动数组卡内存，一直没想到，只会傻呵呵地m*n的矩阵数表，又学到了 (0) sunmoonstar_love 2005-07-11 00:50:11
        之前好几次用滚动数组都砍掉2/3的时间，递推式简单的时候就这么写了，复杂的还是先大数组过了再说 (0) c0500448264 2005-07-11 00:52:45
        P[n][i]是到第n站，油为i时的最少费用，对f不是很明白，f = pri[n]？那方程是不是p[n][i]=min(p[n-1][i+d],p[n][i-1]+pri[i]) (0) sunmoonstar_love 2005-07-11 01:06:25
        f是一litre油要被油站抢劫多少，p是跑到第n个站之后剩i那么多油要多少钱 (0) frkstyc 2005-07-11 01:08:09
        前面抄错了 (0) frkstyc 2005-07-11 01:08:55
        谢谢你 (0) sunmoonstar_love 2005-07-11 01:10:29
        p[n][i]=min(p[n-1][i+d],p[n][i-1]+pri[i]) (19) luoyudong 2010-03-23 21:08:29
  - 谢谢你，能讲讲我错在哪了么，始终想不通为什么WA,WA了20+次 (1633) sunmoonstar_love 2005-07-11 00:33:11
    - 明白了，我对Impossible的判断不够强，郁闷了一晚上，谢谢各位指点~~~~~~~~ (0) sunmoonstar_love 2005-07-11 00:37:35

Post your reply here:

User ID:
Password:
Title:

Content:

> //#include <stdio.h>
> #include<iostream>
> //#include<fstream>
> using namespace std;
> int f[102][201],i,j,k,d,dis[102],sta[102],pri[102],n,inf = 1000000000,tmp;
> 
> int main()
> {
>  //   freopen("in.txt","r",stdin); 
>  //   freopen("out2.txt","w",stdout);
> //    scanf("%d",&d);
> //    ifstream cin("in.txt");
> //    ofstream cout("out2.txt");
>     cin>>d;
>     n = 1;  
>     while(cin>>sta[n]>>pri[n])   
>         n++;
>     sta[n] = d;
>     sta[0] = 0;
>     for(i=1; i<=n; i++)
>     {
>         dis[i]=sta[i]-sta[i-1];
>         if(dis[i]>200 || (i==1||i==n)&&dis[i]>100)
>         {
>             cout<<"Impossible"<<endl;
>             return 0;
>         }    
>         for(j=0; j<=200; j++)
>         {
>             f[i][j] = inf;
>         }    
>     }    
>     f[1][100-sta[1]] = 0;
>     for(i=1; i<n; i++)
>     {
>         for(j=0; j<=200; j++)
>         {
>             if(f[i][j]!=inf)
>             {
>                 for(k=0; k<=200-j; k++)
>                 {
>                     if(j+k>=dis[i+1] && f[i][j]+k*pri[i]<f[i+1][j+k-dis[i+1]])
>                     {
>                         f[i+1][j+k-dis[i+1]] = f[i][j]+k*pri[i];
>                     }    
>                 }    
>             }    
>         }    
>     }
>     cout<<f[n][100]<<endl;    
>   //  printf("%d\n",f[n][100]);
>  //   cin.close();
>  //   cout.close();     
>  //   fclose(stdin); 
>  //   fclose(stdout);   
>     return 0;
> }

Home Page Go Back To top