上周天下午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);
}
}
网友评论