NC244669. 原了个原
描述
输入描述
第一行输入三个正整数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]); }