HDU 5838 Mountain

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5838

题目翻译

对于一张NM高度为1~NM，X为局部最低点，.为普通点，我们定义局部最低点为高度低于周围8个点的点

题解

状态压缩DP+容斥原理
我们从1~NM开始往这张图上面摆放数字，如果这个点是局部最低点，那么在这个点被摆放之前，我们不能摆放其周围的点。
所以我们定义F[i][ST]表示摆到了第i个数字，现在所有的局部最低点的状态时ST。
转移的时候我们分摆放到局部最低点的情况F[i+1][newST]+=F[i][ST]，和摆放在非局部最低点的情况F[i+1][ST]+=F[i][ST](可以摆放的位置数量)
这样DP算出来的F[N*M][FullST]是保证其中规定为局部最低点的点符合的情况。
如此可能有一些不应该是局部最低点也变成局部最低点的情况也被重算了。
于是用DFS枚举所有局部最低点的情况，计算情况数，用容斥组合一下就可以了。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const long long M=772002;
inline void init(){
}
inline bool getMap(){
    char x=getchar();
    while(x!='.' && x!='X') x=getchar();
    if (x=='.') return false;
    return true;
}
inline int lowbit(int x){
    return x&-x;
}
inline long long countST(int ST){
    long long ret=0;
    while(ST){
        ret++;
        ST-=lowbit(ST);
    }
    return ret;
}
int n,m;
bool qmap[10][10];
int tMap[10][10];
int nmb,lmNum,lmST;
long long F[26][(1<<9)];
long long avaBlocks[(1<<9)];
map<pair<int,int>,int> hashValley;
map<int,pair<int,int> > hashPos;
long long Ans;
int CTimes;
inline long long getAns(){
    CTimes++;
    hashValley.clear();
    hashPos.clear();
    nmb=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            //qmap[i][j]=getMap();
            if (qmap[i][j]){
                hashValley[make_pair(i,j)]=++nmb;
                hashPos[nmb]=make_pair(i,j);
            }
        }
    //cout<<"Finished Read"<<endl;
    memset(F,0,sizeof(F));
    lmNum=n*m;
    lmST=(1<<nmb);
    for (int i=1;i<=nmb;i++)
        for (int j=i+1;j<=nmb;j++){
            int x1=hashPos[i].first,y1=hashPos[i].second;
            int x2=hashPos[j].first,y2=hashPos[j].second;
            if (abs(x2-x1)<=1 && abs(y1-y2)<=1){
                //printf("(%d,%d)X(%d,%d)\n",x1,y1,x2,y2);
                //printf("Case #%d: 0\n",T);
                return 0;
            }
        }
    /*for (int i=1;i<=nmb;i++){
        printf("#%d (%d,%d)\n",i,hashPos[i].first,hashPos[i].second);
    }*/
    for (int ST=0;ST<lmST;ST++){
        avaBlocks[ST]=0;
        memset(tMap,0,sizeof(tMap));
        for (int i=1;i<=nmb;i++){
            int x=hashPos[i].first,y=hashPos[i].second;
            tMap[x][y]=1;
            if ((ST&(1<<(i-1)))==0){
                for (int dx=-1;dx<=1;dx++)
                    for (int dy=-1;dy<=1;dy++)
                        if (x+dx>=1 && x+dx<=n && y+dy>=1 && y+dy<=m){
                            tMap[x+dx][y+dy]=1;
                        }
            }
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                avaBlocks[ST]+=(1-tMap[i][j]);
        //printf("State:%d avalibles:%I64d\n",ST,avaBlocks[ST]);
    }
    F[0][0]=1;
    for(int num=0;num<lmNum;num++){
        for (int ST=0;ST<lmST;ST++){
            F[num+1][ST]=(F[num+1][ST]+F[num][ST]*(avaBlocks[ST]-(long long)num+countST(ST)))%M;
            for (int sel=1;sel<=nmb;sel++){
                if ((ST&(1<<(sel-1)))==0){
                    F[num+1][ST|(1<<(sel-1))] = (F[num+1][ST|(1<<(sel-1))] + F[num][ST])%M;
                }
            }
        }
    }
    /*
    for(int num=0;num<=lmNum;num++){
        for (int ST=0;ST<lmST;ST++){
            printf("F[%d][%d]=%I64d\n",num,ST,F[num][ST]);
        }
    }*/
    return F[lmNum][lmST-1];
}
void dfs(long long flag,int x,int y){
    if (y==m+1){
        dfs(flag,x+1,1);
        return;
    }
    if (x>n) {
        long long temp=getAns();
        //printf("%d %I64d\n",flag,temp);
        Ans = (Ans + flag*temp + M)%M;
        return ;
    }
    dfs(flag,x,y+1);
    bool isPossible=true;
    for (int dx=-1;dx<=1;dx++){
        for (int dy=-1;dy<=1;dy++){
            if (x+dx>=1 && x+dx<=n && y+dy>=1 && y+dy<=m)
                if (qmap[x+dx][y+dy]==true){
                    isPossible=false;
                    break;
                }
        }
        if (!isPossible) break;
    }
    if (isPossible){
        qmap[x][y]=true;
        dfs(flag*((long long)-1),x,y+1);
        qmap[x][y]=false;
    }
}
inline void solve(int T){
    CTimes=0;
    //printf("Size:%dX%d\n",n,m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            qmap[i][j]=getMap();
            //if (qmap[i][j]) printf("X"); else printf(".");
        }
        //printf("\n");
    }
    Ans=0;
    //Ans=getAns();
    //printf("BaseAnswer=%I64d\n",Ans);
    dfs(1,1,1);
    printf("Case #%d: %I64d\n",T,Ans);
    //cout<<CTimes<<endl;
}
int main(){
    //freopen("in.txt","r",stdin);
    int T=0;
    while(scanf("%d%d",&n,&m)!=EOF){
        solve(++T);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

#include<cstdio>

#include<iostream>

#include<cstring>

#include<map>

#include<cmath>

#include<algorithm>

using namespace std;

const long long M=772002;

inline void init(){

}

inline bool getMap(){

char x=getchar();

while(x!='.' && x!='X') x=getchar();

if (x=='.') return false;

return true;

}

inline int lowbit(int x){

return x&-x;

}

inline long long countST(int ST){

long long ret=0;

while(ST){

ret++;

ST-=lowbit(ST);

}

return ret;

}

int n,m;

bool qmap[10][10];

int tMap[10][10];

int nmb,lmNum,lmST;

long long F[26][(1<<9)];

long long avaBlocks[(1<<9)];

map<pair<int,int>,int> hashValley;

map<int,pair<int,int> > hashPos;

long long Ans;

int CTimes;

inline long long getAns(){

CTimes++;

hashValley.clear();

hashPos.clear();

nmb=0;

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++){

//qmap[i][j]=getMap();

if (qmap[i][j]){

hashValley[make_pair(i,j)]=++nmb;

hashPos[nmb]=make_pair(i,j);

}

//cout<<"Finished Read"<<endl;

memset(F,0,sizeof(F));

lmNum=n*m;

lmST=(1<<nmb);

for (int i=1;i<=nmb;i++)

for (int j=i+1;j<=nmb;j++){

int x1=hashPos[i].first,y1=hashPos[i].second;

int x2=hashPos[j].first,y2=hashPos[j].second;

if (abs(x2-x1)<=1 && abs(y1-y2)<=1){

//printf("(%d,%d)X(%d,%d)\n",x1,y1,x2,y2);

//printf("Case #%d: 0\n",T);

return 0;

}

/*for (int i=1;i<=nmb;i++){

printf("#%d (%d,%d)\n",i,hashPos[i].first,hashPos[i].second);

}*/

for (int ST=0;ST<lmST;ST++){

avaBlocks[ST]=0;

memset(tMap,0,sizeof(tMap));

for (int i=1;i<=nmb;i++){

int x=hashPos[i].first,y=hashPos[i].second;

tMap[x][y]=1;

if ((ST&(1<<(i-1)))==0){

for (int dx=-1;dx<=1;dx++)

for (int dy=-1;dy<=1;dy++)

if (x+dx>=1 && x+dx<=n && y+dy>=1 && y+dy<=m){

tMap[x+dx][y+dy]=1;

}

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

avaBlocks[ST]+=(1-tMap[i][j]);

//printf("State:%d avalibles:%I64d\n",ST,avaBlocks[ST]);

}

F[0][0]=1;

for(int num=0;num<lmNum;num++){

for (int ST=0;ST<lmST;ST++){

F[num+1][ST]=(F[num+1][ST]+F[num][ST]*(avaBlocks[ST]-(long long)num+countST(ST)))%M;

for (int sel=1;sel<=nmb;sel++){

if ((ST&(1<<(sel-1)))==0){

F[num+1][ST|(1<<(sel-1))] = (F[num+1][ST|(1<<(sel-1))] + F[num][ST])%M;

}

for(int num=0;num<=lmNum;num++){

for (int ST=0;ST<lmST;ST++){

printf("F[%d][%d]=%I64d\n",num,ST,F[num][ST]);

}

}*/

return F[lmNum][lmST-1];

}

void dfs(long long flag,int x,int y){

if (y==m+1){

dfs(flag,x+1,1);

return;

}

if (x>n) {

long long temp=getAns();

//printf("%d %I64d\n",flag,temp);

Ans = (Ans + flag*temp + M)%M;

return ;

}

dfs(flag,x,y+1);

bool isPossible=true;

for (int dx=-1;dx<=1;dx++){

for (int dy=-1;dy<=1;dy++){

if (x+dx>=1 && x+dx<=n && y+dy>=1 && y+dy<=m)

if (qmap[x+dx][y+dy]==true){

isPossible=false;

break;

}

if (!isPossible) break;

}

if (isPossible){

qmap[x][y]=true;

dfs(flag*((long long)-1),x,y+1);

qmap[x][y]=false;

}

inline void solve(int T){

CTimes=0;

//printf("Size:%dX%d\n",n,m);

for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

qmap[i][j]=getMap();

//if (qmap[i][j]) printf("X"); else printf(".");

}

//printf("\n");

}

Ans=0;

//Ans=getAns();

//printf("BaseAnswer=%I64d\n",Ans);

dfs(1,1,1);

printf("Case #%d: %I64d\n",T,Ans);

//cout<<CTimes<<endl;

}

int main(){

//freopen("in.txt","r",stdin);

int T=0;

while(scanf("%d%d",&n,&m)!=EOF){

solve(++T);

}

return 0;

}

WNJXYKの博客

喂你脚下有坑