Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴个0ms状态压缩AC代码

Posted by 15874145100 at 2016-04-13 15:17:40 on Problem 1321
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10
#define M 1<<9-1
int n,m;
int dp[N][M][N];
char ma[N][N];
int dfs(int row,int col,int num)
{
    if(num==m) return 1;
    if(row>=n) return 0;
    if(dp[row][col][num]!=-1) return dp[row][col][num];
    int sum=0;
    for(int i=0;i<n;i++)
    {
        if(ma[row][i]=='#')
        {
            if(col&(1<<i)) continue;
            sum+=dfs(row+1,col|(1<<i),num+1);
        }
    }
    sum+=dfs(row+1,col,num);
    return dp[row][col][num]=sum;
}
int main()
{
    while(~scanf("%d %d",&n,&m)&&n!=-1&&m!=-1)
    {
        for(int i=0; i<n; i++)
              scanf("%s",ma[i]);
        memset(dp,-1,sizeof(dp));
        printf("%d\n",dfs(0,0,0));
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator