[十二省联考2019]皮配(分类讨论的动态规划)-白红宇

[十二省联考2019]皮配(分类讨论的动态规划)

阅读量：7024 次

发布时间：2019-06-28

本文共 3606 字，大约阅读时间需要 12 分钟。

OI考场上正解爆零和不会有什么区别。 --鲁迅

可惜咱连正解都想不到

难得连着部分分加爆搜混了60分

结果

忘清一个数组

$60$->$10$

我枯了

讲解开始

①：有20分爆搜

②：首先考虑k=0的情况

经过简单推理发现：

每个城市选择阵营和每个学校选择派系互不干扰

对于选阵营和选派系各自做一个01背包dp

结果就是二者的合理方案数相乘

③：其次考虑有k的情况

除了“有下属学校有偏好的城市”和“有偏好的学校”以外

其他的学校/城市依然可以按照上面k=0的方法进行背包dp

它们和被偏好限制的城市/学校互不影响

此后考虑对k个偏好的处理

k只有30个，而与此同时... $$s_i$$\leq$ $min$$($$10,M$$)$...$

两种dp的结果的合理方案相乘的加和就是答案

时间复杂度 $O(c*M+n*M+k*(10*k)*M)$

详见代码(领略下精神就好哈)

1 #include
     
        2 #include
      
         3 #include
       
          4 using std::sort;  5 typedef long long lint;  6 const lint mo=998244353;  7 template
        
          st max(st a,st b){
   return a>b?a:b;}  8 template
         
           st min(st a,st b){
   return a
          
           (b.dis!=-1); 18 return a.ct
           
            r?0:(l<=0?dp1[r]:(dp1[r]-dp1[l-1]+mo)%mo); 52 } 53 lint fuck2(int l,int r) 54 { 55 return l>r?0:(l<=0?dp2[r]:(dp2[r]-dp2[l-1]+mo)%mo); 56 } 57 58 int main() 59 { 60 scanf("%d",&T); 61 while(T--) 62 { 63 memclr(); 64 scanf("%d%d",&n,&c); 65 scanf("%d%d%d%d",&c0,&c1,&d0,&d1); 66 for(int i=0;i<=c;i++) ct[i].cnt=ct[i].dis=ct[i].dcnt=0; 67 for(int i=1;i<=n;i++) 68 { 69 scanf("%d%d",&sc[i].ct,&sc[i].cnt); 70 ct[sc[i].ct].cnt+=sc[i].cnt; 71 sum+=sc[i].cnt; 72 sc[i].dis=-1; 73 } 74 scanf("%d",&k); 75 for(int i=1,xin;i<=k;i++) 76 { 77 scanf("%d",&xin); 78 scanf("%d",&sc[xin].dis); 79 ct[sc[xin].ct].dis=1; 80 ct[sc[xin].ct].dcnt+=sc[xin].cnt; 81 sum2+=sc[xin].cnt; 82 } 83 sort(sc+1,sc+1+n); 84 for(int i=1;i<=n;i++)//对于没有偏好限制的学校的背包dp 85 { 86 if(sc[i].dis!=-1) continue; 87 for(int j=d0-sc[i].cnt;j>=0;j--) 88 { 89 dp1[j+sc[i].cnt]=(dp1[j+sc[i].cnt]+dp1[j])%mo; 90 } 91 } 92 for(int i=1;i<=c;i++)//对于没有偏好限制的城市的背包dp 93 { 94 if(ct[i].dis||ct[i].cnt==0) continue; 95 for(int j=c0-ct[i].cnt;j>=0;j--) 96 { 97 dp2[j+ct[i].cnt]=(dp2[j+ct[i].cnt]+dp2[j])%mo; 98 } 99 }100 for(int i=1;i<=d0;i++) dp1[i]=(dp1[i]+dp1[i-1])%mo;//前缀和 101 for(int i=1;i<=c0;i++) dp2[i]=(dp2[i]+dp2[i-1])%mo;//前缀和 102 for(int i=1;i<=k;i++)//分类讨论对于k个有偏好学校的dp 103 {104 for(int j=0;j<=1;j++)105 {106 for(int o=sum2;o>=0;o--)107 {108 for(int p=c0;p>=0;p--)109 {110 dp[i][j][o][p]=0;111 switch(j)112 {113 case 0:114 {115 if(sc[i].dis!=0)116 {117 if(sc[i].ct==sc[i-1].ct)118 {119 add(dp[i][j][o][p],i-1,j,o-sc[i].cnt,p);120 }else121 {122 add(dp[i][j][o][p],i-1,j,o-sc[i].cnt,p-ct[sc[i].ct].cnt);123 add(dp[i][j][o][p],i-1,j^1,o-sc[i].cnt,p-ct[sc[i].ct].cnt);124 }125 }126 if(sc[i].dis!=1)127 {128 if(sc[i].ct==sc[i-1].ct)129 {130 add(dp[i][j][o][p],i-1,j,o,p);131 }else132 {133 add(dp[i][j][o][p],i-1,j,o,p-ct[sc[i].ct].cnt);134 add(dp[i][j][o][p],i-1,j^1,o,p-ct[sc[i].ct].cnt);135 }136 }137 break;138 }139 case 1:140 {141 if(sc[i].dis!=2)142 {143 if(sc[i].ct==sc[i-1].ct)144 {145 add(dp[i][j][o][p],i-1,j,o-sc[i].cnt,p);146 }else147 {148 add(dp[i][j][o][p],i-1,j,o-sc[i].cnt,p);149 add(dp[i][j][o][p],i-1,j^1,o-sc[i].cnt,p);150 }151 }152 if(sc[i].dis!=3)153 {154 if(sc[i].ct==sc[i-1].ct)155 {156 add(dp[i][j][o][p],i-1,j,o,p);157 }else158 {159 add(dp[i][j][o][p],i-1,j,o,p);160 add(dp[i][j][o][p],i-1,j^1,o,p);161 }162 }163 break;164 }165 }166 }167 }168 }169 }170 int mic=sum-c1,mid=sum-d1;171 if(mic>c0||mid>d0)172 {173 printf("0\n");174 continue;175 }176 lint ans=0;177 for(int i=0;i<=c0;i++)178 {179 for(int j=0;j<=sum2;j++)180 {181 lint vv=(dp[k][0][j][i]+dp[k][1][j][i])%mo;182 if(vv)183 {184 ans=(ans+vv*((fuck1(mid-j,d0-j)*fuck2(mic-i,c0-i))%mo)%mo)%mo;//将合理方案相乘后加给答案 185 }186 }187 }188 printf("%lld\n",ans);189 }190 return 0;191 }