HDU 5937 Equation

题意：
有1~9数字各有a1, a2, …, a9个, 有无穷多的+和=.
问只用这些数字, 最多能组成多少个不同的等式x+y=z, 其中x,y,z∈[1,9].
等式中只要有一个数字不一样就是不一样的

思路：
计算下可以发现, 等式最多只有36个.
然后每个数字i的上界是17-i个可以预先判掉答案一定是36的, 然后直接暴力搜索每个等式要不要就好了.
注意剪枝即可

 const int maxn = ;

 int a[maxn];

 bool flag36;

 int ans;

 struct Equation

 {

     int x, y, z;

 } type[];

 void init()

 {

     flag36 = true;

     ans = ;

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

     {

         scanf("%d", a + i);

         if (a[i] <  - i)

         {

             flag36 = false;

         }

     }

 }

 bool can(int t)

 {

     bool flag1 = false, flag2 = false, flag3 = false;

     bool ret = true;

     if (a[type[t].x] > )

     {

         a[type[t].x]--;

         flag1 = true;

     }

     else ret = false;

     if (ret && a[type[t].y] > )

     {

         a[type[t].y]--;

         flag2 = true;

     }

     else ret = false;

     if (ret && a[type[t].z] > )

     {

         a[type[t].z]--;

         flag3 = true;

     }

     else ret = false;

     a[type[t].x] += flag1;

     a[type[t].y] += flag2;

     a[type[t].z] += flag3;

     return ret;

 }

 void dfs(int t, int cnt) // 判断第t中，已经凑出了cnt个

 {

     if ( - t + cnt <= ans || t == ) return;

     if (can(t))

     {

         a[type[t].x]--;

         a[type[t].y]--;

         a[type[t].z]--;

         ans = max(ans, cnt + );

         dfs(t + , cnt + );

         a[type[t].x]++;

         a[type[t].y]++;

         a[type[t].z]++;

     }

     dfs(t + , cnt);

 }

 void solve()

 {

     if (flag36)

     {

         printf("36\n");

         return;

     }

     dfs(, );

     printf("%d\n", ans);

 }

 int main()

 {

     int idx = ;

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

     {

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

         {

             type[idx++] = (Equation){i, j, i + j};

         }

     }

     int T, kase = ;

     scanf("%d", &T);

     while (T--)

     {

         printf("Case #%d: ", ++kase);

         init();

         solve();

     }

     return ;

 }

巴特西

HDU 5937 Equation

最新文章

热门文章