POJ 1948 Triangular Pastures
http://poj.org/problem?id=1948
自力で解けなかった。
なんか、頭いい方法でDPするらしい。
こんなループのまわし方はどうやったら思いつくのだろうか。
#include <cstdio> #include <math.h> #include <algorithm> using namespace std; const int M_N = 40; const int M_L = 40; int N; int l[M_N]; int sum; bool dp[M_N*M_L/2+1][M_N*M_L/2+1]; int heron(double a, double b, double c){ double s = (a + b + c) / 2.0; return (int)(sqrt(s*(s-a)*(s-b)*(s-c))*100.0); } int main(){ scanf("%d", &N); for(int i = 0; i < N; ++i){ scanf("%d", &l[i]); sum+=l[i]; } dp[0][0] = true; for(int k = 0; k < N; ++k) for(int i = N * M_L / 2 + 1; i >= 0; --i) for(int j = i; j >= 0; --j) if(!dp[i][j]&&(i>=l[k]&&dp[i-l[k]][j]||j>=l[k]&&dp[i][j-l[k]])) dp[i][j] = true; int ans = -1; for(int i=0; i<N*M_L/2+1; ++i) for(int j=0; j<N*M_L/2+1; ++j) if(dp[i][j]) ans = max(ans, heron((double)i, (double)j, (double)(sum-i-j))); printf("%d\n", ans); return 0; }