C++14(g++5.4) 解法, 执行用时: 25ms, 内存消耗: 12152K, 提交时间: 2020-08-23 21:07:07

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[101],b[101],c[101],f[101][101][101][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",&a[i],&b[i],&c[i]);
        if(a[i]>b[i]) swap(a[i],b[i]);
        if(b[i]>c[i]) swap(b[i],c[i]);
        if(a[i]>b[i]) swap(a[i],b[i]);
    }
    for(int k=1;k<=m;k++)
     for(int i=1;i<=n;i++)
      for(int j=0;j<i;j++)
       for(int l=0;l<=2;l++)
       {
            int aa,bb,cc;
            if(l==0) aa=a[i],bb=b[i],cc=c[i];
            else if(l==1) aa=a[i],bb=c[i],cc=b[i];
            else aa=b[i],bb=c[i],cc=a[i];    
            if(aa<=a[j]&&bb<=b[j])  f[k][i][i][l]=max(f[k][i][i][l],f[k][i-1][j][0]+cc);
            if(aa<=a[j]&&bb<=c[j])  f[k][i][i][l]=max(f[k][i][i][l],f[k][i-1][j][1]+cc);
            if(aa<=b[j]&&bb<=c[j])  f[k][i][i][l]=max(f[k][i][i][l],f[k][i-1][j][2]+cc);
            f[k][i][i][l]=max(f[k][i][i][l],f[k-1][i-1][j][0]+cc);
            f[k][i][i][l]=max(f[k][i][i][l],f[k-1][i-1][j][1]+cc);
            f[k][i][i][l]=max(f[k][i][i][l],f[k-1][i-1][j][2]+cc);
            f[k][i][j][l]=f[k][i-1][j][l];
       }
    int ans=0;
    for(int i=1;i<=n;i++)
     for(int j=0;j<=2;j++)
       ans=max(ans,f[m][n][i][j]);
    printf("%d",ans);
}

C++(clang++ 11.0.1) 解法, 执行用时: 27ms, 内存消耗: 452K, 提交时间: 2022-10-23 15:41:20

#include<bits/stdc++.h>
using namespace std;
int a[123][3],ans,dp[123][123][3],n,m,x,y,X,Y;
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++)for(int j=1;j<=n;j++)for(int h=0;h<j;h++)for(int k=0;k<=2;k++)for(int l=0;l<=2;l++){
		x=max(a[h][k],a[h][(k+1)%3]),y=min(a[h][k],a[h][(k+1)%3]),X=max(a[j][l],a[j][(l+1)%3]),Y=min(a[j][l],a[j][(l+1)%3]);
		if(x>=X&&y>=Y)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<<ans;
}