BZOJ1079: [SCOI2008]着色方案 (记忆化搜索)

题意:有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。
　　所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两
　　个相邻木块颜色不同的着色方案。

题解:写爆搜妥妥的tle 但是看一眼dp数组应该就秒懂了...

　　还能涂一个的颜色有几种还能涂两个的颜色剩几种....

　　就是一个ez的记忆化搜索了

总结:感觉这道题还是挺套路的直接爆搜是不行的但是发现有许多状态其实是一样的

　　比如当前还剩下两种颜色能涂一次其实并不关心这两种颜色到底是什么只记录一下这一种状态就可以大大减少时间复杂度

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + ;

ll ans;

int k;

int sum;

int vis[];

ll dp[][][][][][];

ll dfs(int a, int b, int c, int d, int e, int use)

{

    if(dp[a][b][c][d][e][use]) return dp[a][b][c][d][e][use];

    ll tmp = ;

    if(a) tmp += 1LL * (use ==  ? a -  : a) * dfs(a - , b, c, d, e, ) % mod;

    if(b) tmp += 1LL * (use ==  ? b -  : b) * dfs(a + , b - , c, d, e, ) % mod;

    if(c) tmp += 1LL * (use ==  ? c -  : c) * dfs(a, b + , c - , d, e, ) % mod;

    if(d) tmp += 1LL * (use ==  ? d -  : d) * dfs(a, b, c + , d - , e, ) % mod;

    if(e) tmp += 1LL * e * dfs(a, b, c, d + , e - , ) % mod;

    tmp %= mod;

    dp[a][b][c][d][e][use] = tmp;

    return tmp;

}

int main()

{

    int x;

    scanf("%d", &k);

    for(int i = ; i <= k; i++) scanf("%d", &x), vis[x]++;

    dp[][][][][][] = ;

    printf("%lld\n", dfs(vis[], vis[], vis[], vis[], vis[], ));

    return ;

}

巴特西

BZOJ1079: [SCOI2008]着色方案 (记忆化搜索)

最新文章

热门文章