#1595 : Numbers
描述
给定n个整数常数c[1], c[2], ..., c[n]和一个整数k。现在需要给2k个整数变量x[1], x[2], ..., x[k], y[1], y[2], ..., y[k]赋值，满足
（1）对于所有1 ≤ i ≤ k，都有x[i] ≤ y[i]。
（2）对于所有1 ≤ i ≤ n，都存在至少一个j (1 ≤ j ≤ k)，使得x[j] ≤ c[i] ≤ y[j]。
求出S=(y[1] + y[2] + ... + y[k]) - (x[1] + x[2] + ... + x[k])的最小值。
输入
第一行两个整数n, k。(1 ≤ n, k ≤ 100000)
接下来n行，每行一个整数c[i]。 (-1000000000 ≤ c[i] ≤ 1000000000)
输出
输出一个整数表示S的最小值。
样例解释
x[1]=-5, y[1]=4,
x[2]=10, y[2]=10.
- 样例输入
5 2
-5
0
10
4
0- 样例输出
9
首先，如果k≥n则可以零距离夹住每个c，此时答案为0。
当k<n时，只需将n个数字从小到大排序，去掉其中最长的k-1个间隔即可。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long long c[], d[];
int cmp(const void * x, const void * y) {
return *((long long *) x) > *((long long *) y);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int n, k;
scanf("%d%d", &n, &k);
for (int i = ; i < n; i++) {
scanf("%lld", &c[i]);
}
if (k >= n) {
printf("0\n");
return ;
}
qsort(c, n, sizeof(long long), cmp);
for (int i = ; i < n - ; i++) {
d[i] = c[i + ] - c[i];
}
qsort(d, n - , sizeof(long long), cmp);
long long ans = c[n - ] - c[];
for (int i = , j = n - ; i < k; i++, j--) {
ans -= d[j];
}
printf("%lld\n", ans);
return ;
}
#1596 : Beautiful Sequence
描述
对于一个正整数列a[1], ... , a[n] (n ≥ 3)，如果对于所有2 ≤ i ≤ n - 1，都有a[i-1] + a[i+1] ≥ 2 × a[i]，则称这个数列是美丽的。
现在有一个正整数列b[1], ..., b[n]，请计算：将b数列均匀随机打乱之后，得到的数列是美丽的概率P。
你只需要输出（P × (n!)）mod 1000000007即可。（显然P × (n!)一定是个整数）
输入
第一行一个整数n。 (3 ≤ n ≤ 60)
接下来n行，每行一个整数b[i]。 (1 ≤ b[i] ≤ 1000000000)
输出
输出（P × (n!)）mod 1000000007。
- 样例输入
4
1
2
1
3- 样例输出
8
满足美丽性质的序列形状为V字形，即先递减后递增，单调序列可以理解为左边或右边长度为0的V字形。
V字形最低点的数字一定是数列中最小的数字，把数列按从小到大的顺序依次添加到两端，只要保证每次添加时和该端最边上的两个数字满足美丽性质，即可实现美丽数列的构造。
首先按从小到大的顺序排序
令dp[i][j][k][l]为当前的数列最左边的两个的下标分别为ij，最右边的两个数字的下标分别为kl时的美丽数列个数。若i=j，表示右边没有了；若k=l，表示左边没有了。
可以通过一个四重循环ijkl实现状态转移，第一重表示当前要添加下标为i的数字，显然，此时数列最左端或最右端的数字中一定有一个编号为i-1，用三重循环jkl枚举另外三个数字。i-1在左边或右边分两种情况，每种情况下各自可能将i添加到左边或右边，一共四次判断，复杂度为O(n^4)。
再想一想的话，其实在循环i时，两端的四个数字里除了必定有一个i-1之外，i-2肯定也在其中，所以其实只用枚举另外两个数字就行了，这种情况下要写八次判断，复杂度为O(n^3)，应该也是可以的，不过没有试。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n;
long long dp[][][][], a[];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%lld", &a[i]);
}
for (int i = ; i < n; i++) {
for (int j = i + ; j < n; j++) {
if (a[i] > a[j]) {
long long t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
int cnt = ;
for (int i = ; i < n; i++) {
if (a[i] == a[]) {
cnt++;
}
}
for (int i = ; i < n; i++) {
a[i] = a[i + cnt - ];
}
n = n - cnt + ;
memset(dp, , sizeof(dp));
dp[][][][] = dp[][][][] = dp[][][][] = ;
for (int i = ; i < n; i++) {
for (int j = ; j < i; j++) {
for (int k = ; k < i; k++) {
for (int l = ; l < i; l++) {
//dp[i-1,j,k,l]
if (i - != j && k != l) {
if ((long long)(a[i] + a[j]) >= (long long)( * a[i - ])) {
dp[i][i - ][k][l] += dp[i - ][j][k][l];
dp[i][i - ][k][l] %= ;
}
if ((long long)(a[k] + a[i]) >= (long long)( * a[l])) {
dp[i - ][j][l][i] += dp[i - ][j][k][l];
dp[i - ][j][l][i] %= ;
}
}
//dp[j,k,l,i-1]
if (j != k && l != i - ) {
if ((long long)(a[i] + a[k]) >= (long long)( * a[j])) {
dp[i][j][l][i - ] += dp[j][k][l][i - ];
dp[i][j][l][i - ] %= ;
}
if ((long long)(a[l] + a[i]) >= (long long)( * a[i - ])) {
dp[j][k][i - ][i] += dp[j][k][l][i - ];
dp[j][k][i - ][i] %= ;
}
}
}
}
}
}
long long ans = ;
if (n > ) {
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
for (int k = ; k < n; k++) {
ans += dp[n - ][i][j][k];
ans += dp[i][j][k][n - ];
ans %= ;
}
}
}
} else {
ans = ;
}
for (int i = ; i <= cnt; i++) {
ans = (ans * i) % ;
}
printf("%lld\n", ans);
return ;
}