CodeForces 366C 动态规划 转化背包思想
2024-08-29 06:53:40
这道题目昨晚比赛没做出来,昨晚隐约觉得就是个动态规划,但是没想到怎么DP,今天想了一下,突然有个点子,即局部最优子结构为 1-j,j<i,遍历i,每次从所有的1到j当中的最优解里面与当前商品进行匹配,若匹配成功,遍判断是否要加。。。。结果WA了,想了一下,确实不对,因为题目的限制条件是所有美味值的总和除以所有卡路里总和一定要==k,这个就好麻烦了,根本不是我定义的那种子结构最优即可,任意后面的状态都可影响前面,所以规划方向无法确定。。。其实这个时候就应该想到用背包问题,背包也是商品挑选,但规划方向无法确定。。。所以通过这个题目,意识到了背包的强大,把上一阶段的所有可能值,下一阶段再进行最优择选,但同时保留所有可能值,以此来防止漏掉情况
其实代码我是看了一个博客之后才写出来的
首先就是要解决==k这个问题,在背包里面怎么表示==k,其实可以转化为 a[i]-k*b[i]==0,也就是说,最终背包的结果就是背包值为0的时候,但是由于这个相减的值可能为负数,所以只能人工+N,以N代替0。
以dp[i][j]表示在第i件物品,在第j个状态(即a[i]-k*b[i])(当然人工+N了)的最大美味值。
则每件物品的时候,遍历整个背包,把所有可能情况都保留下来。
最后只要 dp[n][N]就是结果
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100000
#define INF -900000
using namespace std;
int dp[][N<<];
int a[];
int b[];
int n,k; int main()
{
while (scanf("%d%d",&n,&k)!=EOF)
{
int i,j;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
for (i=;i<=n;i++)
{
scanf("%d",&b[i]);
} for (i=;i<=n;i++)
{
for (j=;j<=N*;j++)
dp[i][j]=INF;
}
dp[][N]=;
int ans=-;
for (i=;i<n;i++)
{
for(j=;j<N*;j++)
{
int temp=a[i+]-k*b[i+];
if (j+temp< || j+temp>=N*) continue;
if (dp[i][j]==INF) continue;
dp[i+][j+temp]=max(dp[i+][j+temp],dp[i][j]+a[i+]);
dp[i+][j]=max(dp[i+][j],dp[i][j]);//本身的状态要记录好
}
}
if (dp[n][N]==)
ans=-;
else
ans=dp[n][N];
printf("%d\n",ans);
}
return ;
}
最新文章
- jquery手写实现单页滚动导航
- linux命令:crontab命令(转)
- [原创]cocos2d-x研习录-第三阶 特性之动作
- SSH配置免密码登陆
- 更换mysql数据目录后出现ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock' (2) 的解决办法
- osg实例介绍
- C#获取程序路径
- 优化DB2缓冲页的大小
- 模板引擎 Velocity
- C#中使用like和in参数传值
- request的getServletPath(),getContextPath(),getRequestURI(),getRealPath(";/";)区别
- freemarker写select组件报错总结(三)
- CCA更新流程分析
- 【linux】---常用命令整理
- 【转】手把手教你读取Android版微信和手Q的聊天记录(仅作技术研究学习)
- MHA-Atlas-MySQL高可用集群
- jsonp 简单封装
- JavaEE 之 WebService
- Errors occurred during the build. Errors running builder &#39;Validation&#39; on pro
- ASP.NET Web API 框架研究 Controller创建 HttpController 类型解析 选择 创建