记录编号	575581	评测结果	WWWWWWWWWW
题目名称	[NOI 1997]积木游戏	最终得分	0
用户昵称	Skloud	是否通过	未通过
代码语言	C++	运行时间	0.039 s
提交时间	2022-09-21 21:25:21	内存使用	1.18 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,ans;
int g[N][4];
int f[N][N][4];
bool check(int x,int opt,int y,int k){
    int p,q,r=g[y][k],s=g[y][k+1>3?1:k+1];
    p=g[x][opt],q=g[x][opt+1>3?1:opt+1];
    if (r<=p&&s<=q)return 1;
    if (s<=p&&r<=q)return 1;
    return 0;
}
int mxx(int x,int y){
    return max(f[x][y][1],max(f[x][y][2],f[x][y][3]));
}
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",&g[i][1],&g[i][2],&g[i][3]);
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            for (int k=j-1;k<i;k++)for(int l=1;l<=3;l++)
                f[j][i][l]=max(f[j][i][l],mxx(j-1,k)+g[i][l+2>3?1:l+2]);
            for (int k=j;k<i;k++)
                for (int p=1;p<=3;p++)
                    for(int l=1;l<=3;l++)
                    if (check(k,p,i,l))
                        f[j][i][1]=max(f[j][i][1],f[j][k][p]+g[i][l+2>3?1:l+2]);
        }
    for (int i=m;i<=n;i++)ans=max(ans,mxx(m,i));
    printf("%d\n",ans);
    return 0;
}