https://www.luogu.com.cn/problem/P6008
十分玄学
刚开始打算建森林树形dp,结果不会建立树,看了题解发现合并集合时候乘起来就好,没必要非得建树,想法和树形dp一样
dp1表示画水,dp0表示不用水,由于高的点画了水,连通块的点都会有水,所以高处放水只有一种方案。
由此可以从下往上推,集合相互合并就把答案乘起来,具体看代码把,不好想,很好写。
#include <iostream> #include <vector> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 1e6+111; ll mod = 1e9+7; int n,m; char map[1010][1010]; int id[1010][1010]; int par[maxn]; ll ans[maxn]; int find(int x){ if(par[x] == -1) return x; return par[x] = find(par[x]); } int unin(int x,int y){ int xx = find(x); int yy = find(y); if(xx == yy ){ return 0; } par[yy] = xx; ans[xx] = (ans[yy]*ans[xx])%mod; return 0; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",map[i]); } int len = 0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(map[i][j] == '.'){ id[i][j] = ++len; } } } for(int i=0;i<=len+100;i++){ par[i] = -1; ans[i] = 1; } for(int i = n-1;i>=0;i--){ for(int j=0;j<m;j++){ if(i != n-1){ if(map[i][j] == '.' && map[i+1][j] == '.'){ unin(id[i][j],id[i+1][j]); } } if(j != 0){ if(map[i][j] == '.' && map[i][j-1] == '.'){ unin(id[i][j],id[i][j-1]); } } } for(int j=0;j<m;j++){ if(map[i][j] == '.'){ int x = id[i][j]; if(par[x] == -1){ ans[x] = (ans[x]+1)%mod; } } } } ll chal = 1; for(int i=1;i<=len;i++){ if(par[i] == -1){ chal = (chal * ans[i])%mod; } } printf("%lld ",chal); return 0; }