3005112_ac_31ms_464k.cc

做的POJ的一些题目

/* f[i][j]±íʾµÚiÐУ¬·½¸ñÅŲ¼Îª¶þ½øÖÆÊýj£¨µÚkλÉÏΪ1±íʾ͹³öÒ»¸ö¸ñ×Ó£¬Îª0±íʾ²»Í¹³ö£©
   µÄ·½°¸Êý¡£ÓÃDFS½øÐÐ״̬תÒÆ¡£*/
#include <iostream>
long long f[12][2048], n, m;
void dfs(int i, int j, int jj, int s)//jÊdzõʼ״̬£¬jjÊÇÄ¿±ê״̬.s±íʾÁÐÊý
{
    if (s == m)//°ÑiÐÐmÁзźà 
        f[i + 1][jj] += f[i][j];//µÈÓÚI+1Ðб»Õ¼È¥µÄ¸ñ×ÓµÄ2½øÖÆΪJJÓ¦¸Ã¿ÉÒÔ¶à·Åf[i][j]µÄ·½ÂÔ 
    else if ((jj & (1 << s)) == 0)//±íʾµÚJÁÐÄÜ·Å1/0 
    {
        dfs(i, j, jj | (1 << s), s + 1);//·Å1 
        if (s < m - 1 && (jj & (1 << (s + 1))) == 0) dfs(i, j, jj, s + 2);//·Å0£¨ºáÕ¼2¸ñ£© 
    }
    else//±íʾ´Ë´¦Ö»ÄÜ·Å0 
       dfs(i, j, jj & ~(1 << s), s + 1);//(jj & (1 << s)Õâ¸öλÖÃÒѾ­±»Õ¼ 
}
int main()
{
    while (scanf("%d%d", &n, &m), n + m != 0)
    {
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < (1 << m); j++)
                if (f[i][j]) //¼ôÖ¦£¨Îª0ûÓбØÒª¿¼ÂÇ£© 
                    dfs(i, j, j, 0);
        printf("%I64d\n", f[n][0]);//²»Õ¼nÐÐÒ²¼´0~n-1·ÅÂúµÄ·½·¨Êý 
    }
    system("pause");
    return 0;
}