Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

水dp,0ms一次AC,附代妈

Posted by KatrineYang at 2016-07-18 21:15:28 on Problem 1191
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

int MAX = 2147483647;

int MIN(int a, int b){
	if(a > b) return b;
	return a;
}

int main() {
	int N;
	int val[8][8];
	cin >> N;
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < 8; j++){
			cin >> val[i][j];
			val[i][j] *= N;
		}
	}
	int res[16][8][8][8][8] = {0};//res[n][i][j][k][l]: 分成n个,从(i,j)开始,到(k,l)结束
	//必须满足:i<=k, j<=l, k+l-i-j>=n-1
	//要求的是res[N][0][0][7][7]
	//先求sigma
	int sigma = 0;
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < 8; j++){
			sigma += val[i][j]/N;
		}
	}

	//初始值:N=1的情况
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < 8; j++){
			for(int k = i; k < 8; k++){
				for(int l = j; l < 8; l++){
					int temp = 0;
					for(int ii = i; ii <= k; ii++){
						for(int jj = j; jj <= l; jj++){
							temp += val[ii][jj];
						}
					}
					res[1][i][j][k][l] = (temp-sigma)*(temp-sigma);
				}
			}
		}
	}

	for(int n = 2; n <= N; n++){
		for(int i = 0; i < 8; i++){
			for(int j = 0; j < 8; j++){
				for(int k = i; k < 8; k++){
					for(int l = j; l < 8; l++){
						if(k+l-i-j < n-1) continue;
						int temp = MAX;
						for(int t = i; t < k; t++){
							if(t+l-i-j>=n-2) temp = MIN(temp, res[n-1][i][j][t][l] + res[1][t+1][j][k][l]);
							if(k+l-(t+1)-j>=n-2) temp = MIN(temp, res[1][i][j][t][l] + res[n-1][t+1][j][k][l]);
						}
						for(int t = j; t < l; t++){
							if(k+t-i-j>=n-2) temp = MIN(temp, res[n-1][i][j][k][t] + res[1][i][t+1][k][l]);
							if(k+l-i-(t+1)>=n-2) temp = MIN(temp, res[1][i][j][k][t] + res[n-1][i][t+1][k][l]);
						}
						res[n][i][j][k][l] = temp;
					}
				}
			}
		}
	}
	int ans = res[N][0][0][7][7];
	double Ans = sqrt(ans * 1.0)/(N*sqrt(N*1.0));
	printf("%.3lf\n", Ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator