首页 > 其他分享 >【USACO10JAN】Cheese Towers S 奶酪塔 (背包dp)

【USACO10JAN】Cheese Towers S 奶酪塔 (背包dp)

时间:2022-10-30 10:23:33浏览次数:43  
标签:Cheese 背包 Towers max 奶酪 int ans USACO10JAN dp

一种思路奇特的做法。

看到题目容易联想到背包dp,因为看上去很像

但是我们并不知道上面有没有大奶酪。

所以我们不妨倒过来看,从上往下加奶酪。

设 \(dp(i,1/0)\) 表示当前从上往下的累加高度为 \(i\),这之中有/无大奶酪。

显然,当我们考虑新加一个奶酪时,有:

\[\begin{cases} dp(i,0)=\max(dp(i-h_j,0)+v_j)\ \ (h_j<K)\\ dp(i,1)=\max(dp(i-h_j,0)+v_j)\ \ (h_j\geq K) \end{cases}\]

然后对于 \(dp(i,1)\),还有:

\[dp(i,1)=\max(dp(i-\frac{4}{5}h_j,1)+v_j) \]

总的时间复杂度 \(O(nt)\),听说 \(O(n^2t)\) 也能过……

#include<bits/stdc++.h>

#define N 110
#define T 1010

using namespace std;

int n,t,k,ans;
int v[N],h[N];
int dp[T][2];

int main()
{
	scanf("%d%d%d",&n,&t,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&h[i]);
	memset(dp,128,sizeof(dp));
	dp[0][0]=0;
	for(int i=0;i<=t;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i-h[j]>=0)
			{
				if(h[j]<k) dp[i][0]=max(dp[i][0],dp[i-h[j]][0]+v[j]);
				else dp[i][1]=max(dp[i][1],dp[i-h[j]][0]+v[j]);
			}
		}
		for(int j=1;j<=n;j++)
			if(i-h[j]*4/5>=0)
				dp[i][1]=max(dp[i][1],dp[i-h[j]*4/5][1]+v[j]);
		ans=max(ans,max(dp[i][0],dp[i][1]));
	}
	printf("%d\n",ans);
	return 0;
}

标签:Cheese,背包,Towers,max,奶酪,int,ans,USACO10JAN,dp
From: https://www.cnblogs.com/ez-lcw/p/16840587.html

相关文章

  • 【PE806】Nim on Towers of Hanoi(汉诺塔游戏,生成函数)
    PE:ProjectEuler题意:汉诺塔游戏是如下的问题:有三根柱子,第一根柱子套有\(n\)个圆盘,圆盘从上往下半径递增。每次操作可以把套在某根柱子上的最上面的那个圆盘移到另一个......
  • 17.CF739C Alyona and towers 区间合并线段树
    17.CF739CAlyonaandtowers区间合并线段树给定序列,要求支持区间加,以及查询最长先增后减子区间(单峰序列)长度非常典型的区间合并线段树,记录左右起LIS,LCS,单峰洛谷传送门:......
  • 【PE806】Nim on Towers of Hanoi(DP)(生成函数)
    NimonTowersofHanoi题目链接:PE806题目大意一个有n个盘子的汉诺塔,在第i个状态的时候如果三个柱子的盘子个数的异或和是0,就会给i的贡献。求n=100000时候的......
  • C. Alyona and towers
    C.Alyonaandtowers题目大意现在有\(n\)个数,\(m\)个操作,每次区间加一个数,对于每一次操作,你要找出最长的$\a_l...a_r\$,满足\[\existsk\!\in\![l,r],a_l<a_{l+1}<a_......
  • CF739C Alyona and towers 解题报告
    线段树绝世好题。题意:维护区间加,全局最长单峰序列。Solution:维护\(8\)个量。\(lval\):左端点的权值。\(rval\):右端点的权值。\(lmax\):以左端点开始的最长的下降序......