CF1509C-The Sports Festival(CF1509C-The Sports Festival)-其他

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

#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, s;
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[n]);
return 0;
}
————————

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, s;
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[n]);
return 0;
}