「JoyOI1097」MM不哭

2014年10月22日2,5720

描述 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。

样例输入

4
3
2 2
5 8
6 1
8 7

样例输出

数据范围和注释 Hint

注意结果的大小。

题解

JoyOI第一页的题还是直接看JoyOI题解吧

#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;
}

#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;

}

« 「BZOJ2091」The Minima Game 「NOIP模拟赛」土豪聪要请客 »

hzwer.com _ Home | http://hzwer.com

「JoyOI1097」MM不哭

分类目录

热门文章

Myfriends

近期评论