「JoyOI1097」MM不哭
描述 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。
第二行包含一个整数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。
样例输入
4
3
2 2
5 8
6 1
8 7
3
2 2
5 8
6 1
8 7
样例输出
56
数据范围和注释 Hint
注意结果的大小。
题解
JoyOI第一页的题还是直接看JoyOI题解吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,x; ll s[1005],d[1005][1005]; ll f[1005][1005][2]; struct data{int d,w,id;}a[1005]; bool operator<(data a,data b) { return a.d<b.d; } ll cal(int x,int y) { int l=x,r=y; if(l>r)swap(l,r); return s[l-1]+s[n]-s[r]; } ll t(int x,int y) { return abs(a[x].d-a[y].d); } int main() { n=read();x=read(); for(int i=1;i<=n;i++) a[i].d=read(),a[i].w=read(),a[i].id=i; sort(a+1,a+n+1); for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].w; memset(f,127,sizeof(f)); for(int i=1;i<=n;i++) if(a[i].id==x)f[i][i][0]=f[i][i][1]=0; for(int k=1;k<n;k++) for(int l=1;l<=n-k;l++) { int r=l+k; f[l][r][0]=min(f[l+1][r][0]+t(l,l+1)*cal(l+1,r),f[l][r-1][1]+t(r-1,r)*cal(l,r-1)+cal(r,l)*t(r,l)); f[l][r][1]=min(f[l][r-1][1]+t(r-1,r)*cal(l,r-1),f[l+1][r][0]+t(l,l+1)*cal(l+1,r)+cal(l,r)*t(l,r)); } printf("%d",min(f[1][n][0],f[1][n][1])); return 0; } |
Subscribe
计数器 9312918
OI 课件=>
OI 课件=>