成都网站建设易维达好,手机界面设计说明,群晖安装wordpress,wordpress钩子登机
jzoj 5535
题目大意#xff1a;
有一架飞机#xff0c;有n个人要登机#xff0c;每个人的不满值为登机时当前机舱在他所在行前方的人数总和#xff0c;现在可以把飞机分为k个机舱#xff0c;使不满值总和最小
原题#xff1a;
题目描述
小H是机场登机的执行经…登机
jzoj 5535
题目大意
有一架飞机有n个人要登机每个人的不满值为登机时当前机舱在他所在行前方的人数总和现在可以把飞机分为k个机舱使不满值总和最小
原题
题目描述
小H是机场登机的执行经理。他的工作是优化登机流程。飞机上的座位有S行编号从1到s每行有六个座位标记为A到F。 今天 有n个乘客陆续登机第i名乘客的座位在第Ri行则第i名乘客的登机难度等于在他登机时坐在1…R(i-1)行的乘客的人数。 例如如果有10名乘客他们的座位是6A4B2E5F2A3F1C10E8B5A那么他们的登机困难分别是000202,0775则难度总和为23 。 为了降低登机难度小H想要将飞机座位划分为k个区域。每一个区域必须是连续的行。划分成k个区域之后乘客的登机顺序不会改变但是每个乘客的登机难度将只统计该乘客所在区域前面乘客的人数。 例如在上面的例子中如果我们把该平面分成两个区域 5-10行和1-4行 然后在第一区域中的乘客的座位为6A5F10E8B5A在第二区域中的乘客的座位为4B2E2A3F1C这种情况下登机难度综合为6。 现在小H不知道该怎么划分这k个区域才能让乘客的登机难度总和最少。
输入
输入文件第一行包含三个整数NS和k下一行包含n个整数1≤Ri≤S输入保证每一行座位由最多有6名乘客。
输出
输出文件包含一个整数表示登机可能的最小登机难度。
输入样例
10 12 2
6 4 2 5 2 3 1 11 8 5输出样例
6说明
数据范围
40%的数据n100s100 100%的数据n1000s1000, k50, ks
解题思路
先用一个s[i][j]s[i][j]s[i][j]来表示前i排人给第j排人造成的不满值总和 然后用f[i][j]f[i][j]f[i][j]来表示第i行到第j行为一个机舱的不满值总和 则
f[i][j]f[i][j-1]s[j][j]-s[i-1][j];//j-1行加上i~j行给第j行的不满值最后直接DP就可以了
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,m,k,l[1050],s[1050][1050],f[1050][1050],ans[1050][100];
int main()
{scanf(%d %d %d,n,m,k);for (int i1;in;i){scanf(%d,l[i]);for (int j1;ji;j)if (l[j]l[i])s[l[j]][l[i]];}for (int i1;im;i)for (int j1;jm;j)s[i][j]s[i-1][j];//前缀和for (int i1;im;i)for (int j1;jm;j)f[i][j]f[i][j-1]s[j][j]-s[i-1][j];//DPmemset(ans,127/3,sizeof(ans));ans[0][0]0;for (int i1;im;i)for (int j1;jk;j)for (int cj;ci;c)//枚举从那个地方开始一个新的机舱ans[i][j]min(ans[i][j],ans[c-1][j-1]f[c][i]);//DPprintf(%d,ans[m][k]);
}
