描述 Description
在一个数轴上, 有 n 个 MM(绝非恐龙!) 在哭泣 (5555~ 一直哭).
tcboy 也在这个数轴上, 并恰好看到了这一幕, 由于每个 MM 哭都会让 tcboy 损失一定的 rp, 于是 tcboy 有必要去安慰她们.(真命苦啊 T.T)
开始时，tcboy 站在 k 号 MM 的旁边.
现在知道第 i 个 MM 哭泣每秒钟会使 tcboy 降低 w[i] 的 rp (单位 rp/s).
而 tcboy 的行走速度很慢只有 1m/s .
tcboy 安慰 MM 的方式很特别 (怎么安慰随便大家 YY 了..#@\(%^%\)#@), 不需要花费时间.
请计算 tcboy 安慰完所有 MM, 会消耗掉的 rp 的最小值.
输入格式 InputFormat
输入文件的第一行包含一个整数 N，2<=N<=1000，表示 MM 的数量。
第二行包含一个整数 V，1<=V<=N，表示开始时 tcboy 站在几号 MM 的旁边.
接下来的 N 行中，每行包含两个用空格隔开的整数 D 和 W，用来描述每个 MM，其中 0<=D<=1000，0<=W<=1000。D 表示 MM 在数轴上的位置 (单位: m)，W 表示每秒钟会使 tcboy 降低 W 的 rp。
输出格式 OutputFormat
输出只有一行：一个整数，即消耗 rp 之和的最小值。结果不超过 1,000,000,000。
样例输入 SampleInput
5
3
0 5
2 1
3 2
6 10
10 4
样例输出 SampleOutput
158
代码 Code
用 f[1..n][1..n][1..2] 作为动规状态。其中:
f[i][j][1] 表示第 i 个到第 j 个 MM 已安慰且当前位于第 i 个 MM 的位置，消耗的最小能量。
f[i][j][2] 表示第 i 个到第 j 个 MM 已安慰且当前位于第 j 个 MM 的位置，消耗的最小能量。
那么转移方程为：
\[ f[i][j][1]=Min\begin{equation} \lbrace \begin{aligned} &f[i+1][j][1]+s[i+1][j]*(d[i+1]-d[i]) \\ &f[i+1][j][2]+s[i+1][j]*(d[j]-d[i]) \\ \end{aligned} \rbrace \end{equation} \]
\[ f[i][j][2]=Min\begin{equation} \lbrace \begin{aligned} &f[i][j-1][1]+s[i][j-1]*(d[j]-d[j-1])\\ &f[i][j-1][2]+s[i][j-1]*(d[j]-d[i])\\ \end{aligned} \rbrace \end{equation} \]
其中 s[i][j] 表示除了 i~j 这段以外，其他的 MM 每秒消耗的总 RP 量。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
struct mm
{
int d,w;
}a[1005];
int s[1005][1005];
int f[1005][1005][5];
int i,j,t,n,m,l,r,k,v,z,y,x;
bool comp(mm a,mm b)
{
return a.d<b.d;
}
void TEST()
{
int i,j,t;
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++) cout<<f[i][j][1]<<" ";
cout<<endl;
for (j=1;j<=n;j++) cout<<" "<<f[i][j][2];
cout<<endl;
}
}
int main()
{
scanf("%d%d",&n,&v);
for (i=1;i<=n;i++) scanf("%d%d",&a[i].d,&a[i].w);
sort(a+1,a+n+1,comp);
t=0;
for (i=1;i<=n;i++)
{
s[i][i]=a[i].w;
t+=s[i][i];
}
for (i=1;i<=n;i++)
{
s[i][i]=t-s[i][i];
for (j=i+1;j<=n;j++) s[i][j]=s[i][j-1]-s[j][j];
}
f[v][v][1]=f[v][v][2]=0;
for (i=v+1;i<=n;i++)
{
f[v][i][2]=f[v][i-1][2]+(a[i].d-a[i-1].d)*s[v][i-1];
f[v][i][1]=f[v][i][2]+(a[i].d-a[v].d)*s[v][i];
}
for (i=v-1;i>=1;i--)
{
f[i][v][1]=f[i+1][v][1]+(a[i+1].d-a[i].d)*(s[i+1][v]);
f[i][v][2]=f[i][v][1]+(a[v].d-a[i].d)*(s[i][v]);
}
for (i=v-1;i>=1;i--) for (j=v+1;j<=n;j++)
{
f[i][j][1]=min(f[i+1][j][1]+s[i+1][j]*(a[i+1].d-a[i].d),f[i+1][j][2]+s[i+1][j]*(a[j].d-a[i].d));
f[i][j][2]=min(f[i][j-1][2]+s[i][j-1]*(a[j].d-a[j-1].d),f[i][j-1][1]+s[i][j-1]*(a[j].d-a[i].d));
}
printf("%d\n",min(f[1][n][1],f[1][n][2]));
return 0;
}