【BZOJ 1505】[NOI2004] 小H的小屋

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1505

仍然是决策单调性QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100+9;
const int MX = 100;

double f[2][MAXN][MAXN],k1,k2;
int n,m,sz[MAXN],sta=1;

#define cal_up(l,r) (k1*((r)-(l))*((r)-(l)))

inline double cal_down(int l, int r, int t){
	int len = r-l, tmp = 0; double ret = 0;
	for (int i=1;i<=t;i++) sz[i] = len/t, tmp += sz[i];
	while (tmp < len) for (int i=1;i<=t && tmp < len;i++) sz[i]++, tmp++;
	for (int i=1;i<=t;i++) ret += k2*sz[i]*sz[i];
	return ret; 
}

inline void Dynamic_Programing(int w, int t){
	for (int i=1;i<=MX;i++) memset(f[w][i],0,sizeof(f[w][i]));
	for (int j=1,t1=1,t2=1;j<=n;j++,t1=1,t2=1) for (int i=1;i<=MX;i++) if (j <= i) {
		for (int h=max(1,t1-3);h<i;h++) for (int g=max(t2-3,1);g<j;g++) if (f[t][h][g]) {			
			double tmp = f[t][h][g] + cal_up(h,i) + cal_down(h,i,j-g);
			if (!f[w][i][j] || f[w][i][j] > tmp) f[w][i][j] = tmp, t1=h, t2=g;
		}
	}
}

int main(){
	scanf("%lf%lf%d%d",&k1,&k2,&m,&n);
	for (int i=1;i<=MX;i++) for (int j=1,lim=min(n,i);j<=lim;j++)
		f[1][i][j] = cal_up(0,i) + cal_down(0,i,j);
	for (int k=2;k<=m;k++,sta^=1) Dynamic_Programing(sta^1,sta);
	printf("%.1lf\n",f[sta][MX][n]);
	return 0;
}