题意：

FJ开车去买食物，如果他的车上有X份食物。每走一里就花费X元。 城市总共E里路，FJ从0开始走，到E结束（不能往回走），要买K份食物。 城里有N个商店，每个商店的位置是Xi，有Fi份食物，每份Ci元。 问到达E并买K份食物的最小花费。k≤100，n≤100。

题解：

dp。f[i][j]表示现在在第i个商店，在j份食物。f[i][j]=f[i-1][j-k]+k*c[i]+j*(x[i]-x[i-1]),k≤fi。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 110 6 #define INF 1e16 7 #define ll long long 8 using namespace std; 9 10 inline int read(){11     char ch=getchar(); int f=1,x=0;12     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();14     return f*x;15 }16 ll f[2][maxn]; int k,e,n,x,y; struct nd{
   int pos,f,c;}nds[maxn];17 bool cmp(nd a,nd b){
   return a.pos
        
         =1;i--){22         inc(j,0,k){23             f[y][j]=INF;24             inc(l,j,min(j+nds[i].f,k))25                 f[y][j]=min(f[y][j],f[x][l]+(ll)(l-j)*nds[i].c+(ll)(nds[i+1].pos-nds[i].pos)*l);26         }27         swap(x,y);28     }29     printf("%lld",f[x][0]); return 0;30 }
        
       
      
     

 

20161011