 /**//*
如图,两条斜线,斜率分别为mk,nk
先要对[0,100]划分,上面的分m个,下面的分n个,m<=n <=100
要求上面划分的点下面也有,点均是整点
求各矩形面积之和最小
dp[m,n,x] 表示[0,x]上面划分了m个,下面划分了n个最优值
转移是枚举上面的最后一块的长度,以及划分了多少个小块
dp[m,n,x] = min{dp[m-1,n-k,x-len] + cost[k,len]}
cost[k,len]表示长度为len,分为k小块的最小代价,可预处理处理
朴素的话要 100^5,超时
我搞了一下午打算用斜率优化搞
这里转移跟两个变量有关系,搞不出T_T
这题杨戈论文《从<小H的小屋>的解法谈算法的优化》里有
在确定了len,枚举k时,
dp[m-1,n-k,x-len] + cost[k,len]是一个抛物线,
而当len增大时,也是一个抛物线,而且最低点的k'不会比之前的k小
这样,记录上次枚举到的k,下次从这里开始,不回溯
降了一维

但我还不是很懂@_@
为什么会是抛物线,以及最低点k不会比之前k的小 ????

那篇文章还提到贪心算法的
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>

using namespace std;


#define sqr(x) ((x)*(x))

double dp[2][101][101], cost[101][101];

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif

double mk, nk;
int M,N;
 for (; ~scanf("%lf%lf%d%d", &mk, &nk, &M, &N);) {

fill(cost[0], cost[1], 1e20);
cost[0][0] = 0.0;
 for(int i = 1; i <= N; i++) {//貌似这个用斜率优化,效果不大,比起下面的循环,小得多
 for(int j = i; j <= 100; j++) {
cost[i][j] = 1e20;
 for(int k = j - 1 ; k >= i-1; k-- ) {
cost[i][j] = min(cost[i][j], cost[i-1][k] + sqr(j-k)*nk);
}
}
}
 for (int i = 1 ; i <= N; i ++) {
 for (int j = 1; j <= 100; j ++) {
cost[i][j] += sqr(j)*mk;
}
}
int now = 0, pre = 1;
fill(dp[0][0], dp[1][0], 1e20);
dp[0][0][0] = 0.0;

 for (int m = 1; m <= M; m++) {
swap(now, pre);
fill(dp[now][0], dp[now+1][0], 1e20);//注意要对无效状态赋初值!!
 for (int n = m; n <= N; n++) {
 for(int x = n; x <= 100; x++) {
 for(int len = 1, last = 1; x - len >= m - 1; len++) {
 for(int k = 1; k <= len && n - k >= m-1; k++) {//从上次最优位置开始 k = last
 if(dp[pre][n-k][x-len] + cost[k][len] < dp[now][n][x]) {
dp[now][n][x] = dp[pre][n-k][x-len] + cost[k][len];
last = k;
}
}
}
}
}
}

printf("%.1f\n", dp[now][N][100]);
}
return 0;
}



|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|