Topcoder 658 650 point-白红宇

Topcoder 658 650 point

阅读量：5286 次

发布时间：2019-06-14

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

Topcoder 658 div2 500 加强版

不过给了<=20，暴力肯定不行。

然后想DP方程，先二分可能需要的最大次数mid;

然后根据 mid 构造 DP方程。

假设x[i]需要 x个9 ，y个3，z个1，x*9+y*3+z>=x[i];

然后求出dp[n][[x]][y][z]<=mid 是否符合。

转移方程为：dp[i+1][n9+m9][m3+n3]=min(dp[i+1][n9+m9][n3+m3],dp[i][n9][n3]+max(0,x[i]-9*m9-3*m3));

（i<n，m9+n9<=mid,m3+n3<=mid）

这里是5维

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 14 #include 
                  
                   15 #include 
                   
                    16 17 using namespace std;18 19 int dp[22][151][151];20 21 class Mutalisk22 {23 public:24 int minimalAttacks(vector 
                    
                      x)25 {26 27 int r=150,l=0;28 int n=x.size();29 for (int _=1;_<20;_++)30 {31 int mid=(l+r)>>1;32 memset(dp,1,sizeof(dp));33 dp[0][0][0]=0;34 35 for (int i=0;i
                     
                      mid ) continue;40 41 for (int m9=0;m9*9<=x[i]+8&&m9+n9<=mid;m9++)42 for (int m3=0;m3*3+m9*9<=max(m9*9,x[i]+2)&&m3+n3<=mid;m3++)43 {44 if (m9+m3+max(0,x[i]-9*m9-3*m3)>mid) continue;45 dp[i+1][n9+m9][m3+n3]=min(dp[i+1][n9+m9][n3+m3],dp[i][n9][n3]+max(0,x[i]-9*m9-3*m3));46 }47 }48 49 int ok=0;50 for (int n9=0;!ok&&n9<=mid;n9++)51 for (int n3=0;!ok&&n3<=mid;n3++)52 if (dp[n][n9][n3]<=mid)53 {54 ok=1;55 }56 57 if (ok) r=mid;58 else l=mid;59 }60 return r;61 }62 };63 64 int main()65 {66 int n;67 cin>>n;68 vector
                      
                        p;69 for (int i=1;i<=n;i++)70 {71 int x;72 cin>>x;73 p.push_back(x);74 }75 Mutalisk q;76 cout<
                       
                        <