【CodeForces - 1282B2 B2. K for the Price of One (Hard Version)】题目
有n件物品，每一件的价格为ai，你有m枚钱，你可以选择买一件，或者买k件并支付最大价值的那件的价格
dp[i]是由前一件或前k件状态转移：dp[i]=min(dp[i-1]+a[i],dp[i-k]+a[i])
由于排序所以所以dp[i]表示花费到第i件的最小花费
AC代码：
package 练习;
import java.io.*;
import java.math.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int N=200005;
static int a[];
static int dp[]=new int [N];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();
t>0;
t--){
int n=sc.nextInt();
int p=sc.nextInt();
int k=sc.nextInt();
a=new int [n+1];
for(int i=1;
i<=n;
i++){
dp[i]=0;
a[i]=sc.nextInt();
}
Arrays.sort(a);
//排序
for(int i=1;
i<=n;
i++){//状态转化
if(i=1;
i--){
if(dp[i]<=p) {
ans=i;
break;
}
}
System.out.println(ans);
}
}
} 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）