Bovine Accordion and Banjo Orchestra G"/>
P6203 [USACO07CHN] The Bovine Accordion and Banjo Orchestra G
翻译:
题目描述
FJ 的 2N 头奶牛(3≤N≤1000)准备举办一场音乐会。其中 N 头奶牛是手风琴手,另外 N 头奶牛是班卓琴手,每个手风琴手有一个天才指数 Ai(0≤Ai≤1000),每个班卓琴手也有一个天才指数 Bi(0≤Bi≤1000)。
FJ 需要给手风琴手和班卓琴手配对。让第 i 位手风琴手和第 j 位班卓琴手配对,能产生 Ai×Bj 的收益。
不幸的是,FJ 的奶牛都存在一种怪癖:如果第 i 位手风琴手和第 j 位班卓琴手配对,那么第 i+1∼N 位手风琴手,不会选择与第 1∼j−1 位班卓琴手配对。这给 FJ 的配对计划带来了很多不便。
更糟糕的是,那些失去演出机会的失落的奶牛,为了消解内心的失落感情,会成群结队地到酒吧喝酒。
如果第 x 号手风琴手到第 y 号手风琴手都是失落的(x−1 和x+1 号手风琴手不存在或是参加了演出),这些奶牛就会去结队去酒吧喝酒,开销为:2(k=x∑yAk)2
对于班卓琴手,也有类似的规律。
现在 FJ 不得不好好考虑下他的计划了,他想让你算出他的最大的收益。
输入格式
第一行一个整数 N。
接下来 N 行,每行一个整数 Ai。
接下来 N 行,每行一个整数 Bi。
输出格式
输出 FJ 能获得的最大收益。
输入输出样例
输入 #1复制
3 1 1 5 5 1 1
输出 #1复制
17
说明/提示
手风琴手 33 和班卓琴手 11 搭配,收益 2525。
手风琴手 1,21,2 一块喝酒,花费 44。
班卓琴手 2,32,3 一块喝酒,花费 44。
最终收益为 1717。
AC:
#include <bits/stdc++.h>
const int N = 1005;
typedef long long ll;
using namespace std;
//ll a[N], b[N], sa[N], sb[N];
ll f[N][N], ans = LLONG_MIN, n;
int main() {//ios::sync_with_stdio(false);cin.tie(NULL);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i], sa[i] = sa[i - 1] + a[i];for (int i = 1; i <= n; i++)cin >> b[i], sb[i] = sb[i - 1] + b[i];//for (int i = 1; i <= n; i++)// f[i][0] = -sa[i] * sa[i], f[0][i] = -sb[i] * sb[i];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {f[i][j] = a[i] * b[j] - sa[i - 1] * sa[i - 1] - sb[j - 1] * sb[j - 1];if (i > 1) for (int l = 1; l < j; l++)f[i][j] = max(f[i][j], f[i - 1][l] + a[i] * b[j] - (sb[j - 1] - sb[l]) * (sb[j - 1] - sb[l]));if (j > 1) for (int k = 1; k < i; k++)f[i][j] = max(f[i][j], f[k][j - 1] + a[i] * b[j] - (sa[i - 1] - sa[k]) * (sa[i - 1] - sa[k]));ans = max(ans, f[i][j] - (sa[n] - sa[i]) * (sa[n] - sa[i]) - (sb[n] - sb[j]) * (sb[n] - sb[j]));}printf("%lld\n", ans);return 0;
}//(copy)
Bye~
更多推荐
P6203 [USACO07CHN] The Bovine Accordion and Banjo Orchestra G
发布评论