题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2993
题目大意：给定一个长度为n的序列，从其中找连续的长度大于m的子序列使得子序列中的平均值最小。
解题思路：经典斜率优化DP，04年周维的论文《浅谈数形结合思想在信息学竞赛中的应用》有很详细的分析，这里只讲下实现。
本题设子序列长度为x，子序列内和为y，使用单调队列来维护凸包的凸性。每次遍历到新的点时都要先把队尾的凸点给去掉，判断条件是y1 * x2 <= y2 * x1((x1,y1)是队尾的点，(x2,y2)是队尾的前一个点). 然后每次更新答案的时候，要把不可能是最优解的点给去掉，判断条件是y1 * x2 <= y2 * x1((x1,y1)是队头的点，(x2,y2)是队头的后一个点)。
我的第一次ac代码700+ms，第二次加了输入外挂就成312ms了，然后将sum数组从double改成int成281ms，Rank3.
测试数据：
Input:
10 6
6 4 2 10 3 8 5 9 4 1
1 1
1
10 3
1 2 3 1 2 3 4 5 6 1
Output:
6.50
1.00
5.00
C艹代码：
- #include <stdio.h>
- #include <string.h>
- #define MAX 100001
- double ans;
- int sum[MAX],n,len;
- int qu[MAX],head,tail;
- double Solve_DP() {
- int i,j,k,pre,cur;
- double x1,x2,y1,y2;
- ans = 0;
- qu[tail] = 0;
- head = tail = 0;
- for (i = len; i <= n; ++i) {
- cur = i - len;
- while (head < tail) {
- //维护队列内凸包的凸性
- pre = qu[tail];
- x1 = cur - pre;
- y1 = sum[cur] - sum[pre];
- pre = qu[tail-1];
- x2 = cur - pre;
- y2 = sum[cur] - sum[pre];
- if (y1 * x2 <= y2 * x1) tail--;
- else break;
- }
- qu[++tail] = cur;
- while (head < tail) {
- //寻找最优的那个点
- cur = i;
- pre = qu[head];
- x1 = cur - pre;
- y1 = sum[cur] - sum[pre];
- pre = qu[head+1];
- x2 = cur - pre;
- y2 = sum[cur] - sum[pre];
- if (y1 * x2 <= y2 * x1) head++;
- else break;
- }
- pre = qu[head];
- double temp = (sum[i] - sum[pre]) * 1.0 / (i - pre);
- if (temp > ans) ans = temp;
- }
- return ans;
- }
- int Input() {
- char ch = ' ';
- while (ch < '0' || ch > '9')
- ch = getchar();
- int x = 0;
- while (ch >= '0' && ch <= '9')
- x = x * 10 + ch - '0',ch = getchar();
- return x;
- }
- int main()
- {
- int i,j,k;
- while (scanf("%d%d",&n,&len) != EOF) {
- for (i = 1; i <= n; ++i)
- k = Input(),sum[i] = sum[i-1] + k;
- ans = Solve_DP();
- printf("%.2lf\n",ans);
- }
- }
本文ZeroClock原创，但可以转载，因为我们是兄弟。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3507
题目大意：给定一个长度为n的序列，和一个常数m，我们可以将序列分成随意段，每段的权值为sum(arr[i]) + C(x<=i<=y)，求一种划分方法使得整个序列的权值最小.n<=50万。
解题思路：做完Hdu的2829，然后再看这题，一切变得如此简单，用两种方法解。
状态转移方程为: dp[i] = min(dp[j] + (sum[i]-sum[j])^2 + m) (j < i);
方法一：dp[i] = dp[j] + (sum[i]-sum[j])^2 + m = dp[j] + sum[i] * sum[i] + sum[j] * sum[j] - 2 * sum[i] * sum[j] + m;
设y = dp[j] + sum[j] * sum[j],x = sum[j]，那么原式等于:dp[i] = y + 2 * sum[i] * x + m + sum[i] * sum[i],然后套下斜率优化DP模板即可ac。
方法二:方法二使用的优化技巧类似于四边形不等式，用个s[i] 记录dp[i]由前面的哪个状态转移过来，然后枚举的时候只要枚举s[i-1] 到i-1就可以了。
第二种方法似乎比第一种要慢一些，常数比较大。
测试数据：
Input
5 5
5 9 5 7 5
1 1000
1
3 1000
1 3 5
3 0
1 3 5
1 0
100000
OutPut:
230
1001
1081
35
10000000000
C艹代码：
- #include <stdio.h>
- #include <string.h>
- #define MAX 510000
- #define int64 long long
- struct point{
- int64 x,y,c;
- }pot[MAX];
- int n,m,arr[MAX];
- int64 sum[MAX],dp[MAX];
- int qu[MAX],head,tail;
- int CheckIt(int x,int y,int z) {
- point p0 = pot[x],p1 = pot[y],p2 = pot[z];
- return (p0.x -p1.x) * (p0.y - p2.y) - (p0.y - p1.y) * (p0.x - p2.x) <= 0;
- }
- int NotBest(int x,int y,int k) {
- point p0 = pot[x],p1 = pot[y];
- return p0.y - k * p0.x > p1.y - k * p1.x;
- }
- int64 Solve_DP() {
- head = tail = 0;
- qu[tail] = 0;
- pot[0].x = pot[0].y = 0;
- for (int i = 1; i <= n; ++i) {
- pot[i].x = sum[i-1];
- pot[i].y = dp[i-1] + sum[i-1] * sum[i-1];
- while (head <= tail - 1 &&
- CheckIt(qu[tail-1],qu[tail],i)) tail--;
- qu[++tail] = i;
- while (head + 1 <= tail &&
- NotBest(qu[head],qu[head+1],2 * sum[i])) head++;
- int k = qu[head];
- dp[i] = pot[k].y - 2 * sum[i] * pot[k].x + sum[i] * sum[i] + m;
- }
- return dp[n];
- }
- int64 Solve_DP2() {
- for (int64 mmin,i = 1; i <= n; ++i) {
- mmin = -1;
- for (int j = qu[i-1]; j < i; ++j)
- if (mmin == -1 ||
- dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) < mmin) {
- mmin = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]);
- qu[i] = j;
- }
- dp[i] = mmin + m;
- }
- return dp[n];
- }
- int main()
- {
- int i,j,k;
- while (scanf("%d%d",&n,&m) != EOF) {
- for (i = 1; i <= n; ++i)
- scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
- int64 ans = Solve_DP2();
- printf("%lld\n",ans);
- }
- }
本文ZeroClock原创，但可以转载，因为我们是兄弟。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3507
题目大意：给定一个长度为n的序列，和一个常数m，我们可以将序列分成随意段，每段的权值为sum(arr[i]) + C(x<=i<=y)，求一种划分方法使得整个序列的权值最小.n<=50万。
解题思路：做完Hdu的2829，然后再看这题，一切变得如此简单，用两种方法解。
状态转移方程为: dp[i] = min(dp[j] + (sum[i]-sum[j])^2 + m) (j < i);
方法一：dp[i] = dp[j] + (sum[i]-sum[j])^2 + m = dp[j] + sum[i] * sum[i] + sum[j] * sum[j] - 2 * sum[i] * sum[j] + m;
设y = dp[j] + sum[j] * sum[j],x = sum[j]，那么原式等于:dp[i] = y + 2 * sum[i] * x + m + sum[i] * sum[i],然后套下斜率优化DP模板即可ac。
方法二:方法二使用的优化技巧类似于四边形不等式，用个s[i] 记录dp[i]由前面的哪个状态转移过来，然后枚举的时候只要枚举s[i-1] 到i-1就可以了。
第二种方法似乎比第一种要慢一些，常数比较大。
测试数据：
Input
5 5
5 9 5 7 5
1 1000
1
3 1000
1 3 5
3 0
1 3 5
1 0
100000
OutPut:
230
1001
1081
35
10000000000
C艹代码：
- #include <stdio.h>
- #include <string.h>
- #define MAX 510000
- #define int64 long long
- struct point{
- int64 x,y,c;
- }pot[MAX];
- int n,m,arr[MAX];
- int64 sum[MAX],dp[MAX];
- int qu[MAX],head,tail;
- int CheckIt(int x,int y,int z) {
- point p0 = pot[x],p1 = pot[y],p2 = pot[z];
- return (p0.x -p1.x) * (p0.y - p2.y) - (p0.y - p1.y) * (p0.x - p2.x) <= 0;
- }
- int NotBest(int x,int y,int k) {
- point p0 = pot[x],p1 = pot[y];
- return p0.y - k * p0.x > p1.y - k * p1.x;
- }
- int64 Solve_DP() {
- head = tail = 0;
- qu[tail] = 0;
- pot[0].x = pot[0].y = 0;
- for (int i = 1; i <= n; ++i) {
- pot[i].x = sum[i-1];
- pot[i].y = dp[i-1] + sum[i-1] * sum[i-1];
- while (head <= tail - 1 &&
- CheckIt(qu[tail-1],qu[tail],i)) tail--;
- qu[++tail] = i;
- while (head + 1 <= tail &&
- NotBest(qu[head],qu[head+1],2 * sum[i])) head++;
- int k = qu[head];
- dp[i] = pot[k].y - 2 * sum[i] * pot[k].x + sum[i] * sum[i] + m;
- }
- return dp[n];
- }
- int64 Solve_DP2() {
- for (int64 mmin,i = 1; i <= n; ++i) {
- mmin = -1;
- for (int j = qu[i-1]; j < i; ++j)
- if (mmin == -1 ||
- dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) < mmin) {
- mmin = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]);
- qu[i] = j;
- }
- dp[i] = mmin + m;
- }
- return dp[n];
- }
- int main()
- {
- int i,j,k;
- while (scanf("%d%d",&n,&m) != EOF) {
- for (i = 1; i <= n; ++i)
- scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];
- int64 ans = Solve_DP2();
- printf("%lld\n",ans);
- }
- }
本文ZeroClock原创，但可以转载，因为我们是兄弟。