vijos 1061 迎春舞会之三人组舞

2019-11-06 08:26:32

字体：大中小

来源：转载

供稿：网友

背景

HNSDFZ的同学们为了庆祝春节，准备排练一场舞描述

n个人选出3*m人，排成m组，每组3人。站的队形——较矮的2个人站两侧，最高的站中间。从对称学角度来欣赏，左右两个人的身高越接近，则这一组的“残疾程度”越低。计算公式为 h=(a-b)^2 (a、b为较矮的2人的身高) 那么问题来了。现在候选人有n个人，要从他们当中选出3*m个人排舞蹈，要求总体的“残疾程度”最低。格式

输入格式

第一排为m，n。第二排n个数字，保证升序排列。输出格式

输出最小“残疾程度”。样例1

样例输入1

9 40 1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164 样例输出1

23 限制

各个测试点1s 提示

m<=1000,n<=5000 数据保证3*m<=n

不用考虑中间的人,所以决策时是两个两个转移状态.并且如果我们选择了i,那么必定会选择i-1.可以由贪心得到.所以不难写出状态转移方程: f[i][j]=min(f[i-1][j],f[i-2][j-1]+选择两人的值); Code:

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<cstdlib>#include<queue>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fod(i,a,b) for(int i=a;i>=b;i--)using namespace std;const int MAXN=5e3+10;const int MAXM=1e3+10;int f[MAXN][MAXM],a[MAXN],n,m;int main(){ scanf("%d%d",&m,&n); memset(f,63,sizeof(f)); for(int i=n;i>=1;i--) { scanf("%d",&a[i]); f[i][0]=0; } f[0][0]=0; #define sqr(a) (a*a) fo(i,1,n) fo(j,1,min(m,i/3)) f[i][j]=min(f[i-1][j],f[i-2][j-1]+sqr((a[i]-a[i-1]))); PRintf("%d",f[n][m]); return 0;}// 注意由于我们选择的是矮的两个人,所以可能会出现第三人不够的情况,这时我们可以让a[]降序排列

——–和光同尘

上一篇：【寻找最佳小程序】影视评分小工具“豆瓣评分”——产品设计要点及专家评析

下一篇：PKCS5：基于密码的加密规范