POJ 3265 DP
2024-08-25 21:37:36
思路:
f[i][j]表示前i天能做j道题 (是做 不是做完)
if(f[i-1][k])
if(suma[j]-suma[k]+g[i-1][k]<=n)
f[i][j]=1,g[i][j]=min(g[i][j],sumb[j]-sumb[k]);
g[i][j]是转移的代价
当g[i][p]
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,p,A[333],B[333],suma[333],sumb[333];
int g[333][333],f[333][333];
int main(){
scanf("%d%d",&n,&p);
for(int i=1;i<=p;i++){
scanf("%d%d",&A[i],&B[i]);
suma[i]=suma[i-1]+A[i];
sumb[i]=sumb[i-1]+B[i];
}
memset(g,0x3f,sizeof(g));
for(int i=0;i<=p;i++)g[i][0]=0,g[0][i]=0;
f[0][0]=1;
for(int i=1;;i++){
for(int j=1;j<=p;j++)
for(int k=0;k<=j;k++)
if(f[i-1][k])
if(suma[j]-suma[k]+g[i-1][k]<=n)
f[i][j]=1,g[i][j]=min(g[i][j],sumb[j]-sumb[k]);
if(g[i][p]<n){printf("%d\n",i+2);return 0;}
}
}
最新文章
- 安装cocoapods遇到两大坑-Ruby版本升级和Podfile的配置
- Hbase集群master.HMasterCommandLine: Master exiting
- 【荐】PHP采集工具curl快速入门教程
- Oracle数据访问组件ODAC的安装方法:
- D FFF团的怒火
- php 函数ignore_user_abort()
- MongoDB学习笔记-创建、更新、删除文档
- linux服务器下发送邮件
- UML统一建模语言
- EasyUI 调用getSelections方法只能获取到一行的原因
- 2016";百度之星"; - 资格赛(Astar Round1) 1004
- echarts饼图配置模板
- Spark学习笔记11面向对象编程
- php中的session过期思考一二
- Mac 下 Redis 5.0 的卸载与安装
- (转) K-Means聚类的Python实践
- Python制作回合制手游外挂简单教程(上)
- 一本通1669S-Nim
- sqlalchemy 获取计数 count
- 巧用XML配置校验导入Excel的列数据格式