记录编号	185332	评测结果	AAAAAAAAAA
题目名称	[NOI 1997]积木游戏	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.225 s
提交时间	2015-09-06 11:32:39	内存使用	0.36 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
int N,M;
int f[110][110][3]={0};//0代表a-b面在上面，1代表b-c面在上面，2代表a-c面在上面
class miku
{
public:
	int a,b,c;
}B[110];
bool pan2(int a,int b,int c,int d)
{
	if(a>b) swap(a,b);
	if(c>d) swap(c,d);
	return c<=a&&d<=b;
}
bool pan(int t,int p,int j,int k)
{
	int xa,xb,ya,yb;
	if(p==0) xa=B[t].a,xb=B[t].b;
	if(p==1) xa=B[t].b,xb=B[t].c;
	if(p==2) xa=B[t].a,xb=B[t].c;
	if(k==0) ya=B[j].a,yb=B[j].b;
	if(k==1) ya=B[j].b,yb=B[j].c;
	if(k==2) ya=B[j].a,yb=B[j].c;
	return pan2(xa,xb,ya,yb);
}
int height(int i,int type)
{
	if(type==0) return B[i].c;
	if(type==1) return B[i].a;
	else return B[i].b;
}
void DP()
{
	for(int i=1;i<=M;i++)//第几堆积木
		for(int j=1;j<=N;j++)//第几块
			for(int k=0;k<3;k++)
				for(int t=0;t<j;t++)
					for(int p=0;p<3;p++)
					{
						f[i][j][k]=max(f[i][j][k],f[i-1][t][p]+height(j,k));
						if(pan(t,p,j,k)) f[i][j][k]=max(f[i][j][k],f[i][t][p]+height(j,k));
						//cout<<t<<" "<<p<<" "<<j<<" "<<k<<" "<<pan(t,p,j,k)<<endl;
					}
	int ans=0;
	for(int j=1;j<=N;j++)
		for(int t=0;t<3;t++)
			ans=max(ans,f[M][j][t]);
	printf("%d",ans);
}
int main()
{
	freopen("buildinggame.in","r",stdin);
	freopen("buildinggame.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
		scanf("%d%d%d",&B[i].a,&B[i].b,&B[i].c);
	DP();
	return 0;
}