• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu6984]Tree Planting

admin

11月 28, 2021

构造一个01矩阵,其中格子$(i,j)$​​​​​对应于第$ik+j$​​个​​​的位置(其中$0le i<lceilfrac{n}{k}ceil,0le j<k$​​​,位置从0开始编号)​​,那么问题即有以下限制:

1.$(lceilfrac{n}{k}ceil-1,j)$(其中$n-(lceilfrac{n}{k}ceil-1)kle j<k$​不能被选择(强制为0)

2.$forall 1le i<lceilfrac{n}{k}ceil$和$0le j<k$,$(i-1,j)$和$(i,j)$不同时为0

3.$forall 0le i<lceilfrac{n}{k}ceil$和$0le j<k$,$(i,j)$和$(i,(j+1)mod k)$不同时为0

关于这个问题,考虑状压dp,有两种dp方式:

1.从上到下、从左到右dp,dp到$(i,j)$​时记录$(i,[0,j])$​和$(i-1,(j,k))$​的01状态即可,复杂度为$o(n2^{k})$

2.从左到右、从上到下dp,dp到$(i,j)$​时记录$([0,lceilfrac{n}{k}ceil),0),([0,i],j)$​和$((i,lceilfrac{n}{k}ceil),j-1)$​的01状态即可,复杂度为$o(n2^{frac{2n}{k}})$(前者可以初始枚举来方便实现)

将两者合并,即对$k^{2}le 2n$​​和$k^{2}>sqrt{2n}$​​分别使用第1种和第2种方式dp

同时,注意到状态序列中不能存在相邻的1,因此$2^{n}$对应的合法状态数仅为$F_{n+2}$(其中$F$为斐波那契数列),根据通项公式约为$1.618^{n}$​

最终,总复杂度为$o(ncdot 1.618^{sqrt{2n}})$​,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 305
 4 #define M 200005
 5 #define L (1<<24)
 6 #define mod 1000000007
 7 #define ll long long
 8 #define Add(x,y) x=(x+y)%mod
 9 vector<int>v;
10 int t,n,k,ans,w[N],vis[L],id[L],f[N<<1][M];
11 int main(){
12     scanf("%d",&t);
13     while (t--){
14         scanf("%d%d",&n,&k);
15         for(int i=0;i<n;i++)scanf("%d",&w[i]);
16         int r=(n+k-1)/k,c=k;
17         ans=mod-1;
18         if (k*k<=2*n){
19             v.clear();
20             for(int i=0;i<(1<<c);i++){
21                 vis[i]=((vis[i>>1])|((i&3)==3));
22                 if (!vis[i]){
23                     id[i]=v.size();
24                     v.push_back(i);
25                 }
26             }
27             for(int i=0;i<=n;i++)
28                 for(int S=0;S<v.size();S++)f[i][S]=0;
29             f[0][0]=1;
30             for(int i=0;i<n;i++)
31                 for(int S=0;S<v.size();S++){
32                     Add(f[i+1][id[v[S]>>1]],f[i][S]);
33                     if ((v[S]&((1<<c-1)|1))==0)Add(f[i+1][id[(v[S]>>1)|(1<<c-1)]],(ll)w[i]*f[i][S]);
34                 }
35             for(int S=0;S<v.size();S++)Add(ans,f[n][S]);
36         }
37         else{
38             v.clear();
39             for(int i=0;i<(1<<r);i++){
40                 vis[i]=(vis[i>>1])+((i&3)==3);
41                 if (vis[i]<=1){
42                     id[i]=v.size();
43                     v.push_back(i);
44                 }
45             }
46             for(int SS=0;SS<v.size();SS++){
47                 if (vis[v[SS]])continue;
48                 for(int i=0;i<=r*(c-1);i++)
49                     for(int S=0;S<v.size();S++)f[i][S]=0;
50                 f[0][SS]=1;
51                 for(int i=0;i<r;i++)
52                     if (v[SS]&(1<<i))f[0][SS]=(ll)w[i*c]*f[0][SS]%mod;
53                 for(int j=1;j<c;j++)
54                     for(int i=0;i<r;i++){
55                         int k=(j-1)*r+i,pos=i*c+j;
56                         for(int S=0;S<v.size();S++){
57                             Add(f[k+1][id[v[S]>>1]],f[k][S]);
58                             if ((pos<n)&&((v[S]&1)==0)&&((!i)||((v[S]&(1<<r-1))==0)))Add(f[k+1][id[(v[S]>>1)|(1<<r-1)]],(ll)w[pos]*f[k][S]);
59                         }
60                     }
61                 for(int S=0;S<v.size();S++)
62                     if ((v[S]&(v[SS]>>1))==0)Add(ans,f[r*(c-1)][S]);
63             }
64         }
65         printf("%d
",ans);
66     }
67     return 0;
68 } 

View Code

发表回复

您的电子邮箱地址不会被公开。