/**//* 如图,两条斜线,斜率分别为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
搜索
最新评论
|
|