※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「オイラープロジェクト341~350」の編集履歴(バックアップ)一覧に戻る

オイラープロジェクト341~350 - (2012/09/13 (木) 21:14:56) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*問い345
+http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20345
+行と列それぞれで1つのみの要素を選択した場合の要素の合計が最も大きくなるものを、その行列の「行列計( Matrix Sum )」と定義する。例えば、下記の行列での行列計は3315になる。( = 863 + 383 + 343 + 959 + 767) :
+以下略
 
+解法
+動的計画法で一発です。
+こういう簡単な問題ばかりならいいんだけど、難しい問題ばかり並んでるよな、、、
+
+
+ #include<stdio.h>
+ #include<string.h>
+ #include<iostream>
+ const int up=2<<14;
+ int memo[up][15],next[up][15]; 
+ int main(){
+	int data[15],nextP;
+	for(int r=0;r<15;r++){
+		for(int c=0;c<15;c++){
+			scanf("%d",&data[c]);
+			if(r==0)memo[(1<<c)][c]=data[c];
+		}
+		if(r==0)continue;
+		memset(next,0,sizeof(next));
+		for(int p=0;p<up;p++){
+			for(int c=0;c<15;c++){
+				if(memo[p][c]==0)continue;
+				for(int nc=0;nc<15;nc++){
+					if((p&(1<<nc))==0){
+						next[p|(1<<nc)][nc]=std::max(next[p|(1<<nc)][nc],memo[p][c]+data[nc]);
+					}
+				}
+			}
+		}
+		memcpy(memo,next,sizeof(next));
+	}
+	int ans=0;
+	for(int c=0;c<15;c++){
+		ans=std::max(memo[up-1][c],ans);
+	}
+	printf("%d",ans);
+ }