codeJan与青蛙

NC14845. codeJan与青蛙

描述

codeJan喜欢观察世界。有一天，codeJan发现一个非常奇怪的现象。有一些年轻的青蛙聚集在一条直线上的某些位置上，同一个位置可能有多个青蛙。这些青蛙每次只会向前跳一米，并且每只青蛙每跳一次都会发出’WA’的一声。codeJan想在一些青蛙的位置上放置黑洞来收集全部的青蛙。在黑洞位置上的青蛙会直接掉进黑洞中不会发出任何叫声，其余的青蛙经过若干次跳跃都会掉进在它前面的最近的黑洞。因为WA类似WrongAnswer，所以codeJan想要知道他合理地安排黑洞的位置，最少可以听到多少声WA？在听到最少声WA时，需要准备的每个黑洞的容量至少为多少？黑洞的容量体现为可以容纳的青蛙的最大数量，所有黑洞的容量应该都相同。

输入描述

第一行一个正整数T≤20表示测试组数。每组测试样例的第一行是两个正整数n,m，分别表示存在青蛙的位置和可以放置黑洞的数量。接下来n行，每行包含两个正整数a[i],b[i]分别表示第i组青蛙的位置(单位：米)和这个位置上青蛙的数量。

输出描述

对于每组测试用例用一行输出两个正整数分别表示最少可以听到多少声WA和黑洞的最少容量。用空格隔开，行末无空格。

示例1

输入:

输出:

8 6
3 4

说明:

对于第一个样例，只能放在 1 位置，因此听到的 WA 的次数为：1*0+2*1+3*2=8，所有青蛙汇聚在一次，容量至少为 6。
对于第二个样例，可以放在 1 和 4 位置，因此听到的 WA 的次数为：1*0+3*1+2*0=3，1 位置和 2 位置的青蛙汇聚在一起，需要容量为 4；4 位置的青蛙单独在一起，需要容量为 2。因此容量至少为 4

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 508K, 提交时间: 2020-02-15 22:22:31

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pr;
ll a[N],b[N],s1[N],s2[N];
pr f[N][N];
int id[N];
bool cmp(int x,int y)
{
	return a[x]<a[y];
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m,i,j,k;
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]),id[i]=i;
		sort(id+1,id+n+1,cmp);
		for(i=1;i<=n;i++) s1[i]=s1[i-1]+b[id[i]],s2[i]=s2[i-1]+a[id[i]]*b[id[i]];
		memset(f,0x3f,sizeof(f));
		f[0][0]=pr(0,0);
		for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		for(k=0;k<i;k++)
		f[i][j]=min(f[i][j],pr(f[k][j-1].first+s2[i]-s2[k]-a[id[k+1]]*(s1[i]-s1[k]),max(f[k][j-1].second,s1[i]-s1[k])));
		printf("%lld %lld\n",f[n][m].first,f[n][m].second);
	}
	return 0;
}

上一题

下一题

详情