时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

一、题目内容

题目描述

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

输入描述：

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

输出描述：

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

示例1

输入

2
3 1
1 1
2 2
3 3
3 2
1 1
4 2
2 3

输出

8 6
3 4

说明

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

备注：

输入保证 $a[i]\neq a[j](i \neq j)，1 \leq m \leq n \leq 100，1 \leq a[i]，b[i] \leq 10^6$ 。

二、解题思路

要求：1.青蛙一次跳一米并叫一声；2.只能向前跳；3.在“叫”的次数最少的情况下全进黑洞。总结：只要黑洞数量足够，青蛙不动就完美了。
已知测试数据为青蛙小队的位置和数量，我们用结构体（a，包含两个值，first，second）去存储，其中first为位置，second为数量，以位置（first）为标准做升序处理，我们可以发现当只有一个黑洞时，青蛙叫次数是每小组数量乘以位置减去一的值依次叠加（ $\sum_{i = 0}^{i -> n}(a[i].ft - 1) * a[i].sd$ ），有两个以上的黑洞呢？多个黑洞，我们除了固定第一个黑洞在当前测试组的最前序列小队位置之外，需要记录两个以后的情况（计算黑洞在下一个位置以后的青蛙叫次数存在f数组中，黑洞容量存在数组g中），其中条件判断可复用上一个黑洞在当前位置的情况，随后更新黑洞的情况。

代码实操：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define ft first
#define sd second
const int N = 100 + 5;
pair<int, int> a[N];
LL f[N][N];
int g[N][N];
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n,m;
        scanf("%d%d", &n, &m);
        for(int i=1; i <= n; ++i){
            scanf("%d%d", &a[i].ft, &a[i].sd);
            a[i].ft = -a[i].ft;
        }
        sort(a + 1, a + n + 1);
        memset(f, 127, sizeof(f));
        f[1][0]=0;
        for(int i = 1, s = 0; i <= n; ++i){
            f[1][i] = f[1][i-1] + 1LL*g[1][i-1] * (a[i].ft - a[i-1].ft);
            g[1][i] = g[1][i-1] + a[i].sd;
        }
        for(int i = 2; i <= m; ++i) {
            for(int j = i; j <= n; ++j){
                int s0 = 0;
                LL s1  = 0, t;
                for(int k = j; k >= i; --k){
                    s0 += a[k].sd;
                    s1 += 1LL*a[k].sd * (a[j].ft - a[k].ft);
                    t   = f[i-1][k-1] + s1
                    if(t < f[i][j]){
                        f[i][j] = t;
                        g[i][j] = max(s0,g[i-1][k-1]);
                    } else if(t == f[i][j]) {
                        g[i][j] = min(g[i][j], max(s0,g[i-1][k-1]));
                    }
                }
            }
        }
        printf("%lld %d\n",f[m][n],g[m][n]);
    }
}

codeJan与青蛙——动态规划