//用~划出了增加的代码
//#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] && sta[n]<=d)
                                 ~~~~~~~~~
        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 || n==1 && dis[i]>0)
                                                    ~~~~~~~~~~~~~~~~~~~
        {
            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;
}

• 立方也能过啊，我还想了平方的 (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