[Offer收割]程式設計練習賽3 - 題目3 : 智力競賽智力競賽 Problem's Link

 ----------------------------------------------------------------------------

Mean: 

略(中文題).

analyse:

比賽中最先想到的是三維dp，但思考後發現可以壓縮為二維，狀态轉移方程：

dp[i][j]=min(dp[i][j],dp[i][j-(right+fault)]+right)

其中dp[i][j]表示：

到通過第i關為止，在總共隻有j次答題機會的情況下，總共至少需要答對dp[i][j]次

最終answer為dp[n][m].

Time complexity: O(N*M*M)

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2016-03-30-21.00

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

const int N=1010;

LL a[N],dp[N][N];

int main()

{

   int Cas;

   cin>>Cas;

   while(Cas--)

   {

       int n,m,s,t;

       cin>>n>>m>>s>>t;

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

       {

           cin>>a[i];

           fill(dp[i],dp[i]+N,INT_MAX);

       }

       fill(dp[0],dp[0]+N,0);

           int max_right=a[i]/s;

           if(a[i]%s) ++max_right;

           for(int right=0;right<=max_right;++right)

           {

               int dif=a[i]-s*right,fault=0;

               if(dif>0)

               {

                   if(dif%t) fault=dif/t+1;

                   else fault=dif/t;

               }

               fault=max(fault,0);

               for(int chance=m;chance>=right+fault;--chance)

                   dp[i][chance]=min(dp[i][chance],dp[i-1][chance-(right+fault)]+right);

           }

       if(dp[n][m]<INT_MAX)

           cout<<dp[n][m]<<endl;

       else

           cout<<"No"<<endl;

   }

   return 0;

}

/*

/**< 帶注釋版 */

       for(int i=1;i<=n;++i) // 到第i關為止

           //對于本關，答對max_right題時，不算錯題的分值也能通關

           for(int right=0;right<=max_right;++right)  // 枚舉答對的題數

               //答對right題時，需要答錯多少題

               // dp[i][j] ------到本關為止，若隻有chance次答題機會，本關答對了right題，若本關能夠通關，到本關為止總共最少需要答對多少題

               // chance-(right+fault) ----- 總共答題機會為chance，本關用了right+fault次，前面所有關隻有chance-(right+fault)次機會