第一眼: 哇, 这题怎么这么眼熟!
见这道题: GO
传送门: GO
根本就是一样的题目嘛!
反正套路是一样的, 就不说什么废话了, 直接上代码吧.
- #include<bits/stdc++.h>
- using namespace std;
- int read(){
- int x=0,f=1;
- char c=getchar();
- while(!isdigit(c)){
- if(c=='-') f=-1;
- c=getchar();
- }
- while(isdigit(c)){
- x=x*10+c-'0';
- c=getchar();
- }
- return x*f;
- }
- const int N=60;
- int n,c;
- int f[N][N][2];
- int dis[N];
- int v[N],sum[N];
- int d(int i,int j){
- return dis[j]-dis[i];
- }
- int val(int i,int j){
- return sum[n]-sum[j]+sum[i-1];
- }
- int main(){
- n=read();c=read();
- for(int i=1;i<=n;i++){
- dis[i]=read();
- v[i]=read();
- sum[i]=sum[i-1]+v[i];
- }
- memset(f,0x3f,sizeof(f));
- f[c][c][1]=f[c][c][0]=0;
- for(int i=2;i<=n;i++){
- for(int j=1;j+i-1<=n;j++){//(i,j+i-1)
- int k=j+i-1;
- f[j][k][0]=min(f[j][k][0],min(f[j+1][k][0]+val(j+1,k)*d(j,j+1),f[j+1][k][1]+val(j+1,k)*d(j,k)));
- f[j][k][1]=min(f[j][k][1],min(f[j][k-1][1]+val(j,k-1)*d(k-1,k),f[j][k-1][0]+val(j,k-1)*d(j,k)));
- }
- }
- printf("%d",min(f[1][n][0],f[1][n][1]));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3210358.html