玩具

题目大意：

有n个物品，每个物品有自己的代价，相邻的物品不能同时购买，现在有m元，问最多买多少件物品

输入样例

3 8 4 4 5

输出样例

1

数据范围

对于30%的数据，n≤10；
对于60%的数据，n≤100，m≤1000；
对于100%的数据，n≤1000，m≤1000000，单个玩具的价格≤1000。

解题思路：

用$f[i][j][1/0]$来表示前i个物品，买了j个的最小代价，且当前可以/不可以买，然后直接DP就可以了

代码：

#include<cstdio> #define max(a,b) (a)>(b)?(a):(b) using namespace std; int n,m,x,ans,f[1100][1100][3]; int main() {scanf("%d %d",&n,&m);f[0][0][1]=m+1;//在这里加上1方便到时判断for (int i=1;i<=n;++i){scanf("%d",&x);for (int j=0;j<=i;++j){f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0]);//不买，前一个可以买或不买if (x<f[i-1][j-1][1]) f[i][j][0]=f[i-1][j-1][1]-x;//当前买,前一时间必须不买且够钱}}for (int i=1;i<=n;++i)if (f[n][i][1]||f[n][i][0])//判断是否行ans=i;printf("%d",ans); }

总结

以上是生活随笔为你收集整理的【DP】玩具的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。