列表

详情


NC244669. 原了个原

描述

最近一款名为羊了个羊的小游戏很火,热爱玩原神的你根据羊了个羊开发了一款名为原了个原的卡牌类游戏,游戏设定如下。

牌有k种颜色,有7堆由上到下放置的牌,每堆牌都有n张,你有一个大小为7的初始为空的卡槽。

你每次操作可以从任意一堆牌的最上端取走一张牌,放入卡槽之中,如果此时卡槽之中有三张颜色相同的牌,你需要立刻将他们移出游戏,并获得大小为移除这三张牌后卡槽中剩下的牌的颜色的数量的分数。

当卡槽中没有三张颜色相同的牌时,你不能将卡牌从卡槽中移出游戏。

当卡槽之中有7张牌且无法被移出游戏时或者牌堆中所有的牌都被取走时,游戏结束。

请问你最多能获得多少分数?

输入描述

第一行输入三个正整数k,n,分别表示牌的颜色数和每堆牌的数量。

之后的7行,每行n个正整数,其中第i行的第j个正整数cij表示第i个牌堆从上到下第j张牌的颜色。

1 <= k,n <= 8

输出描述

输出一个整数,表示最多能获得的分数。

示例1

输入:

2 3
1 1 2
1 1 1
1 1 2
2 1 2
1 1 2
2 2 1
1 1 2

输出:

6

示例2

输入:

1 8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

输出:

0

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 521ms, 内存消耗: 39564K, 提交时间: 2022-11-22 22:01:08

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;
int dp[N];
int a[10][10];
int b[10],t[10],cnt,col,res;
inline int calc(){
    int res = 0;
    for(int i=1;i<=7;i++) res = ((res<<3)+res) + b[i];
    return res;
}
int dfs(){
    int ans = 0;
    int h = calc();
    if(cnt == 7) {
        // cout<<ans<<"\n";
        //res = max(res,ans);
        dp[h] = 0;
        return 0;
    }
    
    if(h == 0){
        // cout<<ans<<"\n";
        //res = max(res,ans);
        dp[h] = 0;
        return dp[h];
    }
    if(~dp[h]) return dp[h];
    for(int i=1;i<=7;i++) {
        if(b[i] == 0)
        continue;
        t[a[i][b[i]]]++;
        if(t[a[i][b[i]]] == 3) {
            cnt -= 2;
            col --;
            t[a[i][b[i]]] = 0;
            b[i]--;
            ans=max(ans,dfs()+col);
            b[i]++;
            t[a[i][b[i]]] = 2;
            col ++;
            cnt += 2;
        }else {
            if(t[a[i][b[i]]] == 1)
                col++;
            cnt ++;
            b[i] --;
            ans = max(ans,dfs());
            b[i] ++;
            cnt --;
            if(t[a[i][b[i]]] == 1)
                col--;
            t[a[i][b[i]]]--;
        }
    }
    // cout<<ans<<"\n";
    return dp[h] = ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n,k;
    cin>>k>>n;
    for(int i=1;i<=7;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int i=1;i<=7;i++) b[i] = n;
    memset(dp,-1,sizeof(dp));
    cout<<dfs()<<"\n";
}

C++(clang++ 11.0.1) 解法, 执行用时: 531ms, 内存消耗: 19152K, 提交时间: 2022-12-01 13:53:09

#include <bits/stdc++.h>
#define pb push_back
#define ALL(tar) tar.begin(), tar.end()
#define forn(name, b, n) for (int name = (b); name < (n); name++)
#define competition cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<pair<int, ii> > EdgeList;
const ll INF = 0x3f3f3f3f;
const ll MOD = 998244353;
const ll MS = 2e7+10;
int dp[9][9][9][9][9][9][9];
int n,k,g[10][10],cnt,colcnt,num[10];
#define getid(zz) (dp[zz[0]][zz[1]][zz[2]][zz[3]][zz[4]][zz[5]][zz[6]])
int dfs(array<int,7> tt){
	if(cnt==7)return 0;
	if(colcnt==6)return 0;
	if(getid(tt)!=-1)return getid(tt);
	int & ans=getid(tt)=0;
	int oldcnt=cnt;
	int oldcol=colcnt;
	array<int,7> k=tt;
	forn(i,0,7){
		if(tt[i]==n)continue;
		tt[i]++;
		int kk=num[g[i][tt[i]]];
		++num[g[i][tt[i]]];
		++cnt;
		int p=0;
		if(num[g[i][tt[i]]]==3){
			cnt-=3;
			--colcnt;
			p=1;
			num[g[i][tt[i]]]=0;
		}
		else if(num[g[i][tt[i]]]==1)++colcnt;
		ans=max(ans,dfs(tt)+(p?colcnt:0));
		num[g[i][tt[i]]]=kk;
		cnt=oldcnt;
		colcnt=oldcol;
		tt=k;
	}
	return ans;
}
int main()
{
	//freopen("in.txt","r",stdin);
	competition;
	memset(dp,-1,sizeof(dp));
	cin>>k>>n;
	forn(i,0,7)forn(j,0,n)cin>>g[i][n-j];
	array<int,7> tt={};
	dfs(tt);
	printf("%d\n",dp[0][0][0][0][0][0][0]);
}

上一题