手机网站合同,大学生实训网站建设心得,不会代码可以做网站吗,网址申请注册方法正题
题目链接:https://www.luogu.com.cn/problem/P3170 题目大意
给出n∗mn*mn∗m的网格上有一些障碍#xff0c;要求用三个LLL形#xff08;高宽随意#xff0c;不能退化成线段/点#xff09;覆盖格子且LLL形之间不能重叠。
求覆盖方案#xff08;每个LLL形相同…正题
题目链接:https://www.luogu.com.cn/problem/P3170 题目大意
给出n∗mn*mn∗m的网格上有一些障碍要求用三个LLL形高宽随意不能退化成线段/点覆盖格子且LLL形之间不能重叠。
求覆盖方案每个LLL形相同
2≤n,m≤302\leq n,m\leq 302≤n,m≤30 解题思路
一道比模板要简单的插头dpdpdp当然我依旧不会
先是考虑插头的状态每个LLL形的话一个还没有涂完的LLL形可能是右插头或者下插头因为只有三个所以最多只会有333个下插头这样的状态数是Cm3C_m^3Cm3的在500050005000以内。
把这些状态压缩起来然后设fx,y,s,k,0/1f_{x,y,s,k,0/1}fx,y,s,k,0/1表示现在dpdpdp到格子(x,y)(x,y)(x,y)目前下插头状态为sss已经插入了kkk个LLL形作为下插头目前有没有右插头。
转移的话就很简单了如果下一个格子有障碍那它上面就不能有插头如果这个格子上面有插头就分为结束这个下插头变为一个右插头或者不结束。 如果这个格子有右插头那么就不能有上插头。 没有这些限制就能够开一个下插头。
需要注意到行尾的时候可能会还有右插头在最右边加一列障碍就好了。 时间复杂度是O(nmCm3)O(nmC_{m}^3)O(nmCm3)的 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N32,M5100;
ll n,m,cnt,f[N][M][4][2];
ll id[N][N][N],pi[M],pj[M],pk[M];
bool v[N][N];char s[N];
void init(){for(ll i0;im;i)for(ll ji?(i1):0;jm;j)for(ll kj?(j1):0;km;k){id[i][j][k]cnt;pi[cnt]i;pj[cnt]j;pk[cnt]k;}ll p[3];for(ll i0;im;i)for(ll j0;jm;j)for(ll k0;km;k){p[0]i;p[1]j;p[2]k;sort(p,p3);id[i][j][k]id[p[0]][p[1]][p[2]];}return;
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1;in;i){scanf(%s,s1);for(ll j1;jm;j)if(s[j]#)v[i][j]1;}m;for(ll i1;in;i)v[i][m]1;ll g0;f[0][1][0][0]1;init();for(ll p1;pn*m;p){ll x(p-1)/m1,y(p-1)%m1;g^1;memset(f[g],0,sizeof(f[g]));for(ll s1;scnt;s){ll api[s],bpj[s],cpk[s];for(ll k0;k3;k){if(f[!g][s][k][0]){if(!v[x][y]){f[g][s][k][0]f[!g][s][k][0];if(ya)f[g][id[0][b][c]][k][1]f[!g][s][k][0];else if(yb)f[g][id[a][0][c]][k][1]f[!g][s][k][0];else if(yc)f[g][id[a][b][0]][k][1]f[!g][s][k][0];else if(k3) f[g][id[y][b][c]][k1][0]f[!g][s][k][0];}else if(y!ay!by!c)f[g][s][k][0]f[!g][s][k][0];}if(f[!g][s][k][1]!v[x][y]y!ay!by!c){f[g][s][k][1]f[!g][s][k][1];f[g][s][k][0]f[!g][s][k][1];}}}}printf(%lld\n,f[g][1][3][0]);return 0;
}
