TopCoder SRM 648 Div2 ABC

題目鏈接:http://community.topcoder.com/stat?c=problem_statement&pm=13645&rd=16312

題意

給定N和K求滿足下列條件的字符串s

• 字符串中每個字符在集合`{'A','B','C'}'中
• 字符串s中存在K對(i,j)滿足0<=i<j<N而且s[i]<s[j]

不存在返回空字符串

解法

記憶化搜索
vis[i][a][b][kk]表示前i個字符,含有a個A字符,b個B字符,kk對(i,j)
轉移方程

• A字符加一個放到最後vis[i+1][a+1][b][kk]=vis[i][a][b][kk]
• B字符加一個放到最後vis[i+1][a][b+1][kk+a]=vis[i][a][b][kk]
• C字符加一個放到最後vis[i+1][a][b][kk+a+b]=vis[i][a][b][kk]

最後求出字符串即可

public class ABC {
    char ch[]=new char[55];
    int N,K;
    boolean vis[][][][]=new boolean[32][32][32][450];
    boolean dfs(int i,int a,int b,int kk) {
        if(i==N) {
            if(kk==K) return true;
            return false;
        }
        if(vis[i][a][b][kk]) return false;
        vis[i][a][b][kk]=true;
        ch[i]='A';
        if(dfs(i+1,a+1,b,kk)) return true;

        ch[i]='B';
        if(dfs(i+1,a,b+1,kk+a)) return true;

        ch[i]='C';
        if(dfs(i+1,a,b,kk+a+b)) return true;

        return false;
    }
    public String createString(int N, int K) {
        this.N=N; this.K=K;
        if(!dfs(0,0,0,0)) return "";
        String res="";
        for(int i=0;i<N;i++) {
            res+=ch[i];
        }
        return res;
    }
}