美文网首页动态规划
hihocoder#1285 : 智力竞赛

hihocoder#1285 : 智力竞赛

作者: haifengmay | 来源:发表于2016-03-30 10:33 被阅读122次

    上周天下午hihocode有一个[Offer收割]编程练习赛3,由于最近想锻炼一下,遂报名。结果三个小时,只做出了两道,不甚理想。现在将当时怎么提交都不过的题做一个总结。

#1285 : 智力竞赛

时间限制: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

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

输出

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

样例输入

1

2 10 9 1

12 35

样例输出

5

    当时的想法是先求出通关需要答对最多的题数Ans,然后将每一关卡对S取余,并将余数升序排列,最终遍历余数数列,将余数用答错的题算出,并将Ans自减。

    当时的想法并没有考虑到S与T的关系问题,当S%T不为零时,该方法便会出现问题。

    此题应当用动态规划的方法,自底向上求出最优解。其中d[i][j]表示第i关需要的答对的题数,i表示第i关,j表示所用题数。

import java.util.Arrays;

import java.util.Scanner;

public class Main3 {

public static void main(String[] args) {

// TODO Auto-generated method stub

    Scanner keyin = new Scanner(System.in);

    int groupNum = keyin.nextInt();//组数

    for (int i = 0; i < groupNum; i++) {

         keyin.nextLine();

       //读入N、M、S和T

        int N=keyin.nextInt(), M=keyin.nextInt(),

        S=keyin.nextInt(),T=keyin.nextInt();

        keyin.nextLine();

        int[] Ai = new int[N];//读入A1~AN

        for (int j = 0; j < N; j++) {

               Ai[j] = keyin.nextInt();

          }

          passJugement(N, M, S, T, Ai);

        }

    }

   public static void passJugement(int N, int M, int S, int T, int[] Ai) {

        //需要用动态规划来解该题

       int[][] dp = new int[N+1][M+1];

       //设置初始值

       Arrays.fill(dp[0], 0);

       for (int i = 1; i <= N; i++) {

             Arrays.fill(dp[i], 1001);

        }

/**

* d[i][j]表示第i关所用的答对题数,i表示管卡,j表示一共答了多少题

*/

        for (int i = 1; i <= N; i++) {

                int max = (int)Math.ceil(Ai[i-1]/(S+0.0));//第i关最多需要答对max题

                for (int k = 0; k <= max; k++) {

                    int wrong = (int)Math.ceil((Ai[i-1]-k*S+0.0)/T);//第i关答对k题的情况下,需要答错多少题

                     wrong = wrong>=0 ? wrong : 0;

                     for (int left = 0; left<=M-k-wrong; left++) {

                          dp[i][k+wrong+left] = Math.min(dp[i][k+wrong+left], dp[i-1][left]+k);

                      }

             }

     }

      int result = 1001;

      for (int j = 0; j <= M; j++) {

           if(dp[N][j]>=0)result = Math.min(result, dp[N][j]);

      }

      if(result>M) System.out.println("No");

      else System.out.println(result);

    }

}

相关文章

  • hihocoder#1285 : 智力竞赛

    上周天下午hihocode有一个[Offer收割]编程练习赛3,由于最近想锻炼一下,遂报名。结果三个小时,只做...

  • 聪明的勇吉-智力竞赛

    智力竞赛(一) 又到了一年一度的智力竞赛时间啦! 每年的这个时候,幸福小学都会举办全校智力竞赛,首先由各年级进行班...

  • 应为“奥数”正名

    “奥数”是青少年的一种智力竞赛,苏联人首创了"数学奥林匹克"这个名词。在类似的以基础科学为竞赛内容的智力竞赛...

  • 我们这样让实体店变得有趣

    店铺智力竞赛小程序是什么? 是一个微信小程序,用微信扫码后进行智力竞赛答题。这是一个内测版,有很多不足之处,我们期...

  • 为何机器讲话的声音难以动听?但做到了却又令人恐怖

    机器之心Synced 你也许看过IBM Watson在2009年智力竞赛节目Jeopardy!上的精彩表现,又或者...

  • 我第三次赢了,我不是白人至上主义者

    美国知名电视智力竞赛节目《危险边缘(Jeopardy!)》,自1964年创立以来,就广泛受到了观众的热烈欢迎。在每...

  • 痛别赵忠祥

    赵忠祥走了,走的很突然。央视这几位名人,差不多都这样,很奇怪。 我和老赵认识,是1986年的央视【蒲公英智力竞赛】...

  • 小学阶段写日记的方法(二)

    活动日记。家里的智力竞赛,家庭风波,邻居间的纠纷,客人的来访,周末的郊游,学校的晚会,篮球比赛,军训,运动会,商场...

  • 动物的这些冷知识,你知道有多少个?

    最近,英国的智力竞赛节目Panel Game旗下的网站QI向公众发布了一套动态图, 超萌的动物面孔、再配上可爱的表...

  • 应试技术 - 通过PMP考试的秘笈

    考前 战略有讲究 PMP考试考的是对知识体系的掌握和运用,它既 不是智力竞赛,也不是创意PK。因此理解和记忆远...

网友评论

    本文标题:hihocoder#1285 : 智力竞赛

    本文链接:https://www.haomeiwen.com/subject/abgslttx.html