引言

hiho一下第145周,其实看到题目有点无奈,居然是dp,好吧,承认自己好久没做过dp了。

描述

小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<=Ti<=50

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

输出

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

样例输入

1
2 10 9 1
12 35

样例输出

5

##分析
做dp问题,最重要的是推导出其递推式,在本题中则为dp[i][j]=min(dp[i][j],dp[i-1][j]+k),k为作对的题目数,dp[i]为在第i关做对的题目数,j为所做的题目数。
代码如下:

#include<stdio.h>
#include<string.h>
#include<math.h>
#define min(x,y) x>y?y:x
void getQuestions(int N,int M,int S,int T);
void dp(int N,int M,int S,int T,int Ai[]);
int main(void){
	int Q;
	int N,M,S,T;
	int i=0;
	scanf("%d",&Q);
	while(i<Q){
		scanf("%d%d%d%d",&N,&M,&S,&T);
		getQuestions(N,M,S,T);
		i++;
	}
	return 0;
}
void getQuestions(int N,int M,int S,int T){
	int i;
	int array[N];
	for(i=0;i<N;i++){
		scanf("%d",&array[i]);
	}
	dp(N,M,S,T,array);
	

}
void dp(int N,int M,int S,int T,int Ai[]){
	int dp[N+1][M+1];
	int i;
	int j;
	int k;
	int left=0;
	for(i=0;i<N+1;i++){
		for(j=0;j<M+1;j++){
			if(i==0)
				dp[i][j]=0;
			else
				dp[i][j]=1000;
		}
	}
	for(i=1;i<=N;i++){
		int max=(int)ceil(Ai[i-1]/(S+0.0));
		for(k=0;k<=max;k++){
			int wrong=(int)ceil((Ai[i-1]-k*S+0.0)/T);
			wrong=wrong>=0?wrong:0;
			for(left=0;left<=M-k-wrong;left++){
				dp[i][k+wrong+left]=min(dp[i][k+wrong+left],dp[i-1][left]+k);
			}
		}
	}
	int result=1000;
	for(j=1;j<=M;j++){
		result=min(result,dp[N][j]);
	}
	if(result>M)
		printf("No");
	else
		printf("%d",result);

}

总结

用时有点久,但是最终还是做出来了,期间也看了一下别人的思路,dp问题还是挺考验人的,^_^

————没有什么是停不下来的,除了时间