Vijos P 1464ブロックゲーム(ダイナミックプランニング)

P 1464ブロックゲーム
Accepted
ラベル:動的計画NOIP向上グループ1997
背景
1997年全国青少年情報学(コンピュータ)オリンピック競技試験問題
だいにしけん
説明
ブロックゲーム
SERCOIは最近、積み木ゲームを設計した.各プレイヤーにはNブロック番号が1,2,...,Nの直方体積木の順にある.各積み木について、その3つの異なる辺をそれぞれ「a辺」、「b辺」、「c辺」と呼ぶ.
ゲームのルールは以下の通りである:1、Nブロックの積み木からいくつかのブロックを選択し、それらをM(l<=M<=N)スタックに分け、第1スタック、第2スタック...、第Mスタックと呼ぶ.各スタックには少なくとも1つのブロックがあり、K番目のスタックのいずれかのブロックの番号は、K+1番目のスタックのいずれかのブロックの番号(2<=K<=M)よりも大きい.
2.各積み木について、遊技者はそれらを垂直に1本の柱に積み上げ、以下の2つの条件を満たすことを要求する:(1)最上位の積み木を除いて、いずれかの積み木の上面が同じで、他の積み木の下面と接触するだけであり、下の積み木の上面が上の積み木の下面を含むことを要求する.つまり、下のブロックの上面の2対の辺の長さは、それぞれ上のブロックの2対の辺の長さよりも大きいことが要求される.
(2)任意の2つの上下面が接触するブロックについて、下のブロックの番号は上のブロックの番号より小さい.
最後に、一人ずつ積み重ねたM本の柱の高さの和によって勝負が決まる.
あなたが積み上げたM本の柱の高さの和が最大になるように、積み木の案を探してください.
書式設定
入力フォーマット
1行目には2つの正の整数NとM(1<=M<=N<=100)があり、それぞれ積み木の総数と積み重ねる柱の数を表す.この2つの数の間は1つのスペースで区切られています.次に、N行は1からNまでのN個の積み木のサイズで、行ごとに3個あります.1000までの整数は、この積み木a辺、b辺、c辺の長さをそれぞれ表す.同じ行の隣接する2つの数の間に1つのスペースで区切られます.
出力フォーマット
1行のみ、整数で、M本の柱の高さの和を表します.
サンプル1
サンプル入力1[コピー]

4 2
10 5 5
8 7 7
2 2 2
6 6 6

サンプル出力1[コピー]

24

制限
各試験点1 s
ヒント
1997年全国青少年情報学(コンピュータ)オリンピック競技試験問題
だいにしけん
構想
1)タイトルには番号に要求があり、k番目のスタックのいずれかのブロックの番号はk+1番目のスタックのいずれかのブロックより大きく、それぞれのスタックの中で、下のブロックの番号は上のブロックの番号より小さくなければならない.つまり、与えられたブロックについては、取るか取らないかはできるが、順番に取るしかなく、順番に積むしかない
2)積み木の大きさに対する要求は、それぞれの下の積み木が上より大きい
3)DPで,mスタック,nブロックのブロックを列挙し,番号要求を満たす前提で,各ブロックの3辺を列挙する.
4)f[i][j][l]でi番目のスタックj番目のブロックブロックl番目のエッジの最大高さを表す
5)サンプル出力:
第1の山、1枚の積み木(10,5,5)、高さは10です
第2の山、2つの積み木(8,7,7)(6,6,6),高さ14
コード#コード#

#include 
using namespace std;
const int N=110;
int a[N][3],ans;
int dp[N][N][3],n,m,x1,y1,x2,y2;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
     cin>>a[i][0]>>a[i][1]>>a[i][2];
    for(int i=1;i<=m;i++)		// i    
        for(int j=1;j<=n;j++)		// j    
            for(int h=0;h=x2&&y1>=y2)			//                    
                            dp[i][j][l]=max(dp[i][j][l],dp[i][h][k]+a[j][(l+2)%3]);  //    ，     
                        dp[i][j][l]=max(dp[i][j][l],dp[i-1][h][k]+a[j][(l+2)%3]);	//       
                        ans=max(ans,dp[i][j][l]);
                    }
    cout<