个人网站域名选择,网页版梦幻西游吸血鬼怎么过,国际新闻最新消息十条摘抄2022,手机网站建设多少钱一个C. The Sports Festival
题意#xff1a;对于给定的整型数组aaa#xff0c;每次选择其中一个元素aia_iai#xff08;不能重复选择同一元素#xff09;#xff0c;每次计算已选择的元素的极差#xff08;最大元素减最小元素的差#xff09;#xff0c;输出最后极差和…C. The Sports Festival
题意对于给定的整型数组aaa每次选择其中一个元素aia_iai不能重复选择同一元素每次计算已选择的元素的极差最大元素减最小元素的差输出最后极差和的最小可能值
思路赛后补题采用二维动态规划最后一个极差一定是整个数组的极差amax−amina_{max} - a_{min}amax−amin而前一个极差无非有两种情况
剔除最小的元素即整个数组中最大减去最次小剔除最大的元素即整个数组中最次大减去最小
若不剔除两边的元素而是中间的元素的话极差则与最后一个极差一致而最后一个极差一定是最大的极差显然不符合最小化的要求 dp[i][j]dp[i][j]dp[i][j]表示剔除iii个最小元素和jjj个最大元素dp[0][0]dp[0][0]dp[0][0]则表示最后一个极差将数组升序排序后由上面的讨论可得到状态转移方程
dp[i][j]min(dp[i−1][j],d[i][j−1])(an−1−j−ai)dp[i][j] min(dp[i-1][j], d[i][j - 1]) (a_{n-1-j}-a_i)dp[i][j]min(dp[i−1][j],d[i][j−1])(an−1−j−ai)
当ijn−1ij n - 1ijn−1时即说明已完成此时n−1−jin-1-j in−1−ji极差的减数与被减数指向同一元素即最初只选择了一个元素时的情况 最后的答案等于dpdpdp数组中满足ijn−1ij n - 1ijn−1的最小元素值显然有nnn个元素满足条件每个元素即代表了最初选择数组中每个aia_iai所能得到的最小结果
#includebits/stdc.h
#define debug1(x) cout#x:xendl
typedef long long ll;
typedef unsigned long long ull;
const int N 2010;
const int MOD 10000;
using namespace std;
int a[N];
ll dp[N][N];
int main()
{int n;cinn;for(int i 1; i n; i) cina[i];sort(a1, an1);dp[0][0] a[n] - a[1];for(int j 1; j n; j) dp[0][j] dp[0][j-1] (a[n-j] - a[1]);for(int i 1; i n; i) dp[i][0] dp[i-1][0] (a[n] - a[1i]);ll ex;for(int i 1; i n; i){for(int j 1; i j n; j){ex a[n-j] - a[1i];dp[i][j] min(dp[i-1][j], dp[i][j-1]) ex;}}ll ans dp[0][n-1];for(int i 0; i n; i){ans min(ans, dp[i][n-1-i]);}coutans\n;return 0;
}
