Topcoder 658 650 point

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维

 #include <iostream>

 #include <cstdlib>

 #include <algorithm>

 #include <fstream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <deque>

 #include <set>

 using namespace std;

 int dp[][][];

 class  Mutalisk

 {

     public:

     int minimalAttacks(vector <int> x)

     {

         int r=,l=;

         int n=x.size();

         for (int _=;_<;_++)

         {

             int mid=(l+r)>>;

             memset(dp,,sizeof(dp));

             dp[][][]=;

             for (int i=;i<n;i++)

             for (int n9=;n9<=mid;n9++)

             for (int n3=;n3<=mid;n3++)

             {

                 if (dp[i][n9][n3]>mid ) continue;

                 for (int m9=;m9*<=x[i]+&&m9+n9<=mid;m9++)

                 for (int m3=;m3*+m9*<=max(m9*,x[i]+)&&m3+n3<=mid;m3++)

                 {

                     if (m9+m3+max(,x[i]-*m9-*m3)>mid) continue;

                     dp[i+][n9+m9][m3+n3]=min(dp[i+][n9+m9][n3+m3],dp[i][n9][n3]+max(,x[i]-*m9-*m3));

                 }

             }

         int ok=;

         for (int n9=;!ok&&n9<=mid;n9++)

         for (int n3=;!ok&&n3<=mid;n3++)

         if (dp[n][n9][n3]<=mid)

         {

             ok=;

         }

         if (ok) r=mid;

         else l=mid;

         }

         return r;

     }

 };

 int main()

 {

     int n;

     cin>>n;

     vector<int> p;

     for (int i=;i<=n;i++)

     {

         int x;

         cin>>x;

         p.push_back(x);

     }

     Mutalisk q;

     cout<<q.minimalAttacks(p)<<endl;

     return ;

 }

状态，需要剪枝。

巴特西

Topcoder 658 650 point

最新文章

热门文章