AOJ 0089: The Shortest Path on A Rhombic Path

入力してDPをします。上・下から真ん中までそれぞれ計算していって、上下の和が最大になるものを出力します。分からない場合は、まずは上半分だけについて考えてみましょう。(Project Euler に上半分だけの問題があったと思います。)

int data[110][60],dp1[50],dp2[50];
char str[200];
char *result = NULL;
char d[] = ",";

int main(){
	int k1 = 0;
	while(scanf("%s",str) != EOF){
		int k2 = 0;
		result = strtok(str,d);
		while(result != NULL){
			data[k1][k2] = atoi(result);
			result = strtok(NULL,d);
			k2++;
		}
		k1++;
	}

	dp1[0] = data[0][0];
	for(int i = 0; i < k1/2; i++){
		for(int j = i+1; j >= 1; j--){
			dp1[j] = max(dp1[j-1],dp1[j]) + data[i+1][j];
		}
		dp1[0] += data[i+1][0];
	}

	dp2[0] = data[k1-1][0];
	for(int i = k1-1; i > k1/2; i--){
		for(int j = k1-i; j >= 1; j--){
			dp2[j] = max(dp2[j-1],dp2[j]) + data[i-1][j];
		}
		dp2[0] += data[i-1][0];
	}

	int res = 0;
	for(int i = 0; i <= k1/2; i++){
		res = max(res,dp1[i] + dp2[i] - data[k1/2][i]);
	}
	cout<<res<<endl;
	return 0;
}