CF|K for the Price of One (Hard Version)（dp/贪心）线性动态规划|#|贪心算法|#

【CF|K for the Price of One (Hard Version)（dp/贪心）】
文章图片

文章图片

有 n件物品，每一件的价格为ai，你有m枚钱，你可以选择买一件，或者买k件并支付最大价值的那件的价格

显然dp[i]是由前一件或前k件状态转移过来
dp[i]=min(dp[i-1]+a[i],dp[i-k]+a[i]);
dp[i]表示到第i件货物的最小花费（由于排序之后，表示前 i 件货物最小花费）

const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; int dp[N]; int main() { //IOS; rush(){ int n,p,k; sdd(n,p); sd(k); for(i=1; i<=n; i++) cin>>a[i]; sort(a+1,a+1+n); //dp[i]=min(dp[i-1]+a[i],dp[i-k]+a[i]); int pos=0; for(i=1; i<=n; i++){ dp[i]=dp[i-1]+a[i]; if(i>=k) dp[i]=min(dp[i],dp[i-k]+a[i]); //if(dp[i]>p) break; if(dp[i]<=p) pos=i; } pd(pos); } //PAUSE; return 0; }

当然这个题也可以用贪心，和 B1 解法一样
B1. K for the Price of One (Easy Version)（贪心）

const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; int sum[N]; int main() { //IOS; rush(){ int n,p,k; sdd(n,p); sd(k); for(i=1; i<=n; i++) cin>>a[i]; sort(a+1,a+1+n); for(i=1; i=sum[i]) pos=i; pd(pos); } //PAUSE; return 0; }