CF1509C-The Sports Festival(CF1509C-The Sports Festival)

题目链接

题目大意:给出一个序列,问在以一定方法排好序后,每个前缀中最小值跟最大值的差值之和最小为多少。

看代码就知道,是非常基础的区间DP,但第一眼根本没看出来。后来我知道了这是区间DP,但也不知道怎么入手。因为这里面有一个贪心:将原序列从小到大排好序之后,要从一个长度为n的区间的答案得到一个长度为n+1的区间的答案,那么往这个区间里加的数肯定紧邻它的左边或者右边,不然的话差值就大了。这不好证明,也不好想,但知道之后还是比较好理解的。

知道规律之后就一气呵成地打完了,WA。原因是画错了解答树,只考虑了各区间同其右边的数合并的请款,没考虑同其左边的数合并的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long dp[2005][2005], s[2005];
int main()
{
    int n, i, j, len;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%lld", &s[i]);
    sort(s + 1, s + 1 + n);
    for (len = 1; len < n; len++)
    {
        for (i = 1; i + len <= n; i++)
        {
            j = i + len;
            dp[i][j] = min(dp[i][j - 1] + s[j] - s[i], dp[i + 1][j] + s[j] - s[i]);
        }
    }
    printf("%lld", dp[1][n]);
    return 0;
}
————————

Title Link

Give a sequence and ask what is the minimum sum of the difference between the minimum value and the maximum value in each prefix after arranging the sequence in a certain way.

You can see from the code that it is a very basic interval DP, but you don’t see it at first sight. Later, I learned that this was interval DP, but I didn’t know how to start. Because there is a greed: after arranging the original sequence from small to large, you should get the answer of an interval with length N + 1 from the answer of an interval with length N, then the number added to this interval must be close to its left or right, otherwise the difference will be large. It’s hard to prove and think about, but it’s easier to understand after knowing.

Once you know the law, you finish it at one go, WA. The reason is that the wrong understanding answer tree is drawn, which only considers the payment request of each interval combined with the number on the right, but does not consider the combination with the number on the left.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long dp[2005][2005], s[2005];
int main()
{
    int n, i, j, len;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%lld", &s[i]);
    sort(s + 1, s + 1 + n);
    for (len = 1; len < n; len++)
    {
        for (i = 1; i + len <= n; i++)
        {
            j = i + len;
            dp[i][j] = min(dp[i][j - 1] + s[j] - s[i], dp[i + 1][j] + s[j] - s[i]);
        }
    }
    printf("%lld", dp[1][n]);
    return 0;
}