hihocoder-1285 智力竞赛(区间dp)

智力竞赛

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi、小Ho还有被小Hi强拉来的小Z，准备组队参加一个智力竞赛。竞赛采用过关制，共计N个关卡。在第i个关卡中，小Hi他们需要获得Ai点分数才能够进入下一关。每一关的分数都是独立计算的，即使在一关当中获得超过需要的分数，也不会对后面的关卡产生影响。

小Hi他们可以通过答题获得分数。答对一道题获得S点分数，答错一道题获得T点分数。在所有的N个关卡中，小Hi他们一共有M次答题机会。在每个关卡中，都可以在累计答题次数不超过M的情况下使用任意次的答题机会。

那么现在问题来了，对于给定的N、M、S、T和A，小Hi他们至少需要答对多少道题目才能够完成所有的关卡呢？

输入

每个输入文件包含多组测试数据，在每个输入文件的第一行为一个整数Q，表示测试数据的组数。

每组测试数据的第一行为四个正整数N、M、S和T，意义如前文所述。

第二行为N个正整数，分别表示A1~AN。

对于40%的数据，满足1<=N,M<=100

对于100%的数据，满足1<=N,M<=1000,1<=T<S<=10,1<=Ai<=50

对于100%的数据，满足1<=Q<=100

输出

对于每组测试数据，如果小Hi他们能够顺利完成关卡，则输出一个整数Ans，表示小Hi他们至少需要答对的题目数量，否则输出No。

样例输入

样例输出

5

题意：中文的就不说了;
思路：dp[i][j]表示通过第i关,一共用了j次答题机会的最小正确答题次数,话说我好晕不知道不还是区间dp,捂脸...;
AC代码：

#include <iostream>

#include <cstdio>

#include <map>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[][];

const int inf=0x7f7f7f7f;

int n,m,s,t,num,a[];

int main()

{

    int q;

    scanf("%d",&q);

    while(q--)

    {

        memset(dp,inf,sizeof(dp));

        scanf("%d%d%d%d",&n,&m,&s,&t);

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

        {

            dp[][j]=;

        }

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

        {

            scanf("%d",&a[i]);

            if(a[i]%s==)num=a[i]/s;

            else num=a[i]/s+;

            for(int k=;k<=num;k++)

            {

                int x=a[i]-k*s;

                if(x>)

                {

                    if(x%t==)x=x/t;

                    else x=x/t+;

                }

                else x=;//一开始这个地方没写还wa了几发,额的罚时啊啊啊啊

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

                {

                    if(j+k+x<=m)

                    {

                        dp[i][j+k+x]=min(dp[i][j+k+x],dp[i-][j]+k);

                    }

                }

            }

        }

        int ans=inf;

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

        {

            ans=min(ans,dp[n][j]);

        }

        if(ans>m)cout<<"No"<<"\n";

        else cout<<ans<<"\n";

    }

    return ;

}

巴特西

hihocoder-1285 智力竞赛(区间dp)

智力竞赛

描述

输入

输出

最新文章

热门文章