记录编号	575497	评测结果	AAAAAAAAAA
题目名称	[NOI 1997]积木游戏	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2022-09-19 11:11:42	内存使用	0.61 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int l[110][5], f[110][110][5];
int length(int x,int d){
	return max(l[x][d],l[x][d+1]);
}
int width(int x,int d){
	return min(l[x][d],l[x][d+1]);
}
bool check(int x,int d1,int y,int d2){
	return(length(x,d1)<=length(y,d2))&&(width(x,d1)<=width(y,d2));
}
int main(){
	freopen("buildinggame.in","r",stdin);
	freopen("buildinggame.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>l[i][0]>>l[i][1]>>l[i][2];
		l[i][3]=l[i][0];
		l[i][4]=l[i][1];
	}
	for(int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			for(int k=0;k<i;++k){
				for(int d1=0;d1<=2;++d1){
					for(int d2=0;d2<=2;++d2){
						f[i][j][d1]=max(f[i][j][d1],f[k][j-1][d2]+l[i][d1+2]);
						if(check(i,d1,k,d2)){
							f[i][j][d1]=max(f[i][j][d1],f[k][j][d2]+l[i][d1+2]);
						}
						ans=max(ans,f[i][j][d1]);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}