题解 P1879 【[USACO06NOV]玉米田Corn Fields】

· · 题解

来一波0s做法。

显然这是状态压缩dp

定义也是非常的好想，

定义d[i][j]表示决策到了第i行，j记录上一个行的表示情况

那么显然有d[i][j]=sigma(d[i-1][j ban p])(p属于j)

当然实际上采用存在性dp的形式转移。

那么有一个很有趣的问题，如何确定一个横行是合法的？

打表啊~~~~

下面是数据生成器代码

#include<stdio.h>
#include<algorithm>
using namespace std;
int res[100000];int cnt;
void dfs(int x,int step)//简单的dfs没啥好说
{
    if(step==13)
    {
        res[cnt++]=(x>>1);
        return;
    }
    if(((1<<step)&x)==0)
    {
        dfs((x|1<<(step+1)),step+1);
        dfs(x,step+1);
    }
    else 
    {
        dfs(x,step+1);
    }
    return;
}
int main()
{
    dfs(0,0);
    printf("cnt=%d",cnt);
    sort(res,res+cnt);
    for(int i=0;i<cnt;i++)
    {
        if(i%16==0)printf("\n");
        printf("%-5d,",res[i]);
    }
    return 0;
}

然后我们就可以愉快的dp了~ 这个剪枝剪得非常狠，所以超级快~

上代码~

#include<stdio.h>
#include<math.h>
using namespace std;
int dp[20][30000];
int n;int m;int c[20];
int res;bool map[20][20];
int up;
int s[600]={

0 ,1 ,2 ,4 ,5 ,8 ,9 ,10 ,16 ,17 ,18 ,20 ,21 ,32 ,33 ,34 , 36 ,37 ,40 ,41 ,42 ,64 ,65 ,66 ,68 ,69 ,72 ,73 ,74 ,80 ,81 ,82 ,

84 ,85 ,128 ,129 ,130 ,132 ,133 ,136 ,137 ,138 ,144 ,145 ,146 ,148 ,149 ,160 ,

161 ,162 ,164 ,165 ,168 ,169 ,170 ,256 ,257 ,258 ,260 ,261 ,264 ,265 ,266 ,272 ,

273 ,274 ,276 ,277 ,288 ,289 ,290 ,292 ,293 ,296 ,297 ,298 ,320 ,321 ,322 ,324 ,

325 ,328 ,329 ,330 ,336 ,337 ,338 ,340 ,341 ,512 ,513 ,514 ,516 ,517 ,520 ,521 ,

522 ,528 ,529 ,530 ,532 ,533 ,544 ,545 ,546 ,548 ,549 ,552 ,553 ,554 ,576 ,577 ,

578 ,580 ,581 ,584 ,585 ,586 ,592 ,593 ,594 ,596 ,597 ,640 ,641 ,642 ,644 ,645 ,

648 ,649 ,650 ,656 ,657 ,658 ,660 ,661 ,672 ,673 ,674 ,676 ,677 ,680 ,681 ,682 ,

1024 ,1025 ,1026 ,1028 ,1029 ,1032 ,1033 ,1034 ,1040 ,1041 ,1042 ,1044 ,1045 ,1056 ,1057 ,1058 ,

1060 ,1061 ,1064 ,1065 ,1066 ,1088 ,1089 ,1090 ,1092 ,1093 ,1096 ,1097 ,1098 ,1104 ,1105 ,1106 ,

1108 ,1109 ,1152 ,1153 ,1154 ,1156 ,1157 ,1160 ,1161 ,1162 ,1168 ,1169 ,1170 ,1172 ,1173 ,1184 ,

1185 ,1186 ,1188 ,1189 ,1192 ,1193 ,1194 ,1280 ,1281 ,1282 ,1284 ,1285 ,1288 ,1289 ,1290 ,1296 ,

1297 ,1298 ,1300 ,1301 ,1312 ,1313 ,1314 ,1316 ,1317 ,1320 ,1321 ,1322 ,1344 ,1345 ,1346 ,1348 ,

1349 ,1352 ,1353 ,1354 ,1360 ,1361 ,1362 ,1364 ,1365 ,2048 ,2049 ,2050 ,2052 ,2053 ,2056 ,2057 ,

2058 ,2064 ,2065 ,2066 ,2068 ,2069 ,2080 ,2081 ,2082 ,2084 ,2085 ,2088 ,2089 ,2090 ,2112 ,2113 ,

2114 ,2116 ,2117 ,2120 ,2121 ,2122 ,2128 ,2129 ,2130 ,2132 ,2133 ,2176 ,2177 ,2178 ,2180 ,2181 ,

2184 ,2185 ,2186 ,2192 ,2193 ,2194 ,2196 ,2197 ,2208 ,2209 ,2210 ,2212 ,2213 ,2216 ,2217 ,2218 ,

2304 ,2305 ,2306 ,2308 ,2309 ,2312 ,2313 ,2314 ,2320 ,2321 ,2322 ,2324 ,2325 ,2336 ,2337 ,2338 ,

2340 ,2341 ,2344 ,2345 ,2346 ,2368 ,2369 ,2370 ,2372 ,2373 ,2376 ,2377 ,2378 ,2384 ,2385 ,2386 ,

2388 ,2389 ,2560 ,2561 ,2562 ,2564 ,2565 ,2568 ,2569 ,2570 ,2576 ,2577 ,2578 ,2580 ,2581 ,2592 ,

2593 ,2594 ,2596 ,2597 ,2600 ,2601 ,2602 ,2624 ,2625 ,2626 ,2628 ,2629 ,2632 ,2633 ,2634 ,2640 ,

2641 ,2642 ,2644 ,2645 ,2688 ,2689 ,2690 ,2692 ,2693 ,2696 ,2697 ,2698 ,2704 ,2705 ,2706 ,2708 ,

2709 ,2720 ,2721 ,2722 ,2724 ,2725 ,2728 ,2729 ,2730 ,4100 ,4101 ,4104 ,4105 ,4106 ,4112 ,

4113 ,4114 ,4116 ,4117 ,4128 ,4129 ,4130 ,4132 ,4133 ,4136 ,4137 ,4138 ,4160 ,4161 ,

4162 ,4164 ,4165 ,4168 ,4169 ,4170 ,4176 ,4177 ,4178 ,4180 ,4181 ,4224 ,4225 ,4226 ,4228 ,4229 ,

4232 ,4233 ,4234 ,4240 ,4241 ,4242 ,4244 ,4245 ,4256 ,4257 ,4258 ,4260 ,4261 ,4264 ,4265 ,4266 ,

4352 ,4353 ,4354 ,4356 ,4357 ,4360 ,4361 ,4362 ,4368 ,4369 ,4370 ,4372 ,4373 ,4384 ,4385 ,4386 ,

4388 ,4389 ,4392 ,4393 ,4394 ,4416 ,4417 ,4418 ,4420 ,4421 ,4424 ,4425 ,4426 ,4432 ,4433 ,4434 ,

4436 ,4437 ,4608 ,4609 ,4610 ,4612 ,4613 ,4616 ,4617 ,4618 ,4624 ,4625 ,4626 ,4628 ,4629 ,4640 ,

4641 ,4642 ,4644 ,4645 ,4648 ,4649 ,4650 ,4672 ,4673 ,4674 ,4676 ,4677 ,4680 ,4681 ,4682 ,4688 ,

4689 ,4690 ,4692 ,4693 ,4736 ,4737 ,4738 ,4740 ,4741 ,4744 ,4745 ,4746 ,4752 ,4753 ,4754 ,4756 ,

4757 ,4768 ,4769 ,4770 ,4772 ,4773 ,4776 ,4777 ,4778 ,4096 };//丧心病狂的数据表

int main()
{
        //状压dp都是一样的，这个是模板
    scanf("%d%d",&n,&m);
    up=pow(2,m+1)-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j])
            {
                c[i]+=1<<j;
                //printf("c[%d]=%d\n",i,c[i]);
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=up;j++)
        {
            dp[i][j]=-1;
        }
    }
    dp[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;s[j]<=up;j++)
        {
            if(dp[i][s[j]]!=-1)
            {
                //printf("dp[%d][%d]=%d\n",i,s[j],dp[i][s[j]]);
                for(int k=0;s[k]<=up;k++)
                {
                    if((s[k]&s[j])==0&&(s[k]|c[i+1])==c[i+1])
                    {
                        if(dp[i+1][s[k]]==-1)dp[i+1][s[k]]=0;
                        dp[i+1][s[k]]+=dp[i][s[j]];dp[i+1][s[k]]%=1000000000;
                        //printf("->dp[%d][%d]=%d\n",i+1,s[k],dp[i+1][s[k]]);
                    }
                }
            }
        }
    }
    for(int j=0;s[j]<=up;j++)
    {
        if(dp[n][s[j]]!=-1)
        {
            res+=dp[n][s[j]];
            res%=1000000000;
        }
    }
    printf("%d",res);
    return 0;
}