Miku

这个题目还是挺水得

正确解决方法 $Rightarrow$ 写一个搜索 $Rightarrow$ TLE $Rightarrow$进行记忆化改造 $Rightarrow$ Ac

记忆化搜索和dp个人感觉有个区别就是记忆化是从下往上，dp是从上往下

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[45][45][45][45];
int n;
int can[5][45];
int bas[45];
int cnt;
int dfs(int a,int b,int c,int d){
    if(dp[a][b][c][d])
    return dp[a][b][c][d];
    if(cnt==5)
    return 0;
    if(a<=n){
        if(bas[can[1][a]]){
            bas[can[1][a]]--;
            cnt--;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a+1,b,c,d)+1);
            cnt++;
            bas[can[1][a]]++;
        }else{
            bas[can[1][a]]++;
            cnt++;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a+1,b,c,d));
            bas[can[1][a]]--;
            cnt--;          
        }
    }
    if(b<=n){
        if(bas[can[2][b]]){
            bas[can[2][b]]--;
            cnt--;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a,b+1,c,d)+1);
            cnt++;
            bas[can[2][b]]++;
        }else{
            bas[can[2][b]]++;
            cnt++;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a,b+1,c,d));
            bas[can[2][b]]--;
            cnt--;          
        }
    }
    if(c<=n){
        if(bas[can[3][c]]){
            bas[can[3][c]]--;
            cnt--;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a,b,c+1,d)+1);
            cnt++;
            bas[can[3][c]]++;
        }else{
            bas[can[3][c]]++;
            cnt++;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a,b,c+1,d));
            bas[can[3][c]]--;
            cnt--;          
        }
    }
    if(d<=n){
        if(bas[can[4][d]]){
            bas[can[4][d]]--;
            cnt--;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a,b,c,d+1)+1);
            cnt++;
            bas[can[4][d]]++;
        }else{
            bas[can[4][d]]++;
            cnt++;
            dp[a][b][c][d]=max(dp[a][b][c][d],dfs(a,b,c,d+1));
            bas[can[4][d]]--;
            cnt--;          
        }
    }
    return dp[a][b][c][d];
}
int main(){
    while(cin>>n&&n!=0){
        memset(dp,0,sizeof(dp));
        memset(bas,0,sizeof(bas));
        cnt=0;
        for(int i=1;i<=n;++i){
            cin>>can[1][i]>>can[2][i]>>can[3][i]>>can[4][i];
        }
        dfs(1,1,1,1);
        cout<<dp[1][1][1][1]<<endl;;
    }
    return 0;
}