poj 1948 Triangular Pastures 01背包

其实，之前说背包简单，现在就觉得不是。。郁闷

怎么表示状态还是不简单啊。。这就是所谓的dp的难点？

//用f[i][j][k]表示到第i根木棒能否摆出边长分别为j,k的三角形
//01背包
//f[i][j] = f[i - len][j] | f[i][j - len]
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
bool f[801][801];
int len[40];
int cir;			//周长
double p;			//半周长

int main() {
	//freopen("1.txt", "r", stdin);
	int n;
	while(cin >> n) {
		cir = 0;
		for(int i = 0;i < n; i++) {
			cin >> len[i];
			cir += len[i];
		}
		p = cir / 2.0;
		memset(f, false, sizeof(f));
		f[0][0] = true;
		for(int i = 0; i < n; i++) {
			for(int j = p - 1; j >= 0; j--) {
				for(int k = j; k >= 0; k--) {
					if(len[i] <= j)
						f[j][k] |= f[j - len[i]][k];
					if(len[i] <= k)
						f[j][k] |= f[j][k - len[i]];
				}
			}
		}
		double ans = -1;
		for(int i = 1; i < p - 1; i++) {
			for(int j = 1; j < p - 1; j++) {
				if(f[i][j]) {
					int tmp = cir - i - j;
					double area = p * (p - tmp) * (p - i) * (p - j);
					ans = max(ans, area);
				}
			}
		}
		if(ans > 0) cout << int(sqrt(ans) * 100) << endl;
		else cout << -1 << endl;
	}
 	return 0;
}