 /**//*
如圖,兩條斜線,斜率分別為mk,nk
先要對[0,100]劃分,上面的分m個(gè),下面的分n個(gè),m<=n <=100
要求上面劃分的點(diǎn)下面也有,點(diǎn)均是整點(diǎn)
求各矩形面積之和最小
dp[m,n,x] 表示[0,x]上面劃分了m個(gè),下面劃分了n個(gè)最優(yōu)值
轉(zhuǎn)移是枚舉上面的最后一塊的長度,以及劃分了多少個(gè)小塊
dp[m,n,x] = min{dp[m-1,n-k,x-len] + cost[k,len]}
cost[k,len]表示長度為len,分為k小塊的最小代價(jià),可預(yù)處理處理
樸素的話要 100^5,超時(shí)
我搞了一下午打算用斜率優(yōu)化搞
這里轉(zhuǎn)移跟兩個(gè)變量有關(guān)系,搞不出T_T
這題楊戈論文《從<小H的小屋>的解法談算法的優(yōu)化》里有
在確定了len,枚舉k時(shí),
dp[m-1,n-k,x-len] + cost[k,len]是一個(gè)拋物線,
而當(dāng)len增大時(shí),也是一個(gè)拋物線,而且最低點(diǎn)的k'不會(huì)比之前的k小
這樣,記錄上次枚舉到的k,下次從這里開始,不回溯
降了一維

但我還不是很懂@_@
為什么會(huì)是拋物線,以及最低點(diǎn)k不會(huì)比之前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++) {//貌似這個(gè)用斜率優(yōu)化,效果不大,比起下面的循環(huán),小得多
 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);//注意要對無效狀態(tài)賦初值!!
 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++) {//從上次最優(yōu)位置開始 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
搜索
最新評論

|
|