poj 3265 Problem Solving dp
2024-09-13 15:00:44
这个题目容易让人误以为是贪心就可以解决了,但是细想一下很容易举出反例。
dp[i][j]表示解决了i个问题,最后一个月解决的问题数目。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=3e2+9;
int a[maxn],b[maxn];
int suma[maxn],sumb[maxn];
int dp[maxn][maxn];
int main()
{
// freopen("in.txt","r",stdin);
int m,p;
while(scanf("%d %d",&m,&p)!=EOF)
{
suma[0]=sumb[0]=0;
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(dp,50,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<=p;i++)
for(int j=i;j>=0;j--)
{
for(int k=i;k<=p;k++)
{
if(suma[k]-suma[i]+sumb[i]-sumb[i-j]>m)
break;
if(sumb[k]-sumb[i]>m)
break;
dp[k][k-i]=min(dp[k][k-i],dp[i][j]+1);
}
}
printf("%d\n",dp[p][0]+1);
}
return 0;
}
最新文章
- 【Win10 应用开发】自定义应用标题栏
- 手把手教你玩GDB
- android如何切换皮肤
- ArrayBlockingQueue和LinkedBlockingQueue分析
- C语言的本质(5)——类型转换的本质与处理
- powerdesigner for sqlserver的一些实用配置
- ajax struts2 数据的返回形式
- Android Hal 分析
- springMVC统一异常处理
- slice全解析
- pyCharm最新激活码(2018激活码)
- 前端基础之http协议
- JAVA特性一:封装
- servlet入门与进阶
- Android 不同分辨率下调整界面
- VPS挂机赚美刀详细介绍–Alexamaster操作流程
- Arm-kernel 内存收集【转】
- Java - 避免不必要的对象
- react native运行报错
- 数据库5.7-jdbc版本8.0.12驱动连接
热门文章
- Unity3D NGUI,uGUI总结
- C++经典书目索引及资源下载
- 【Linux】环境变量设置
- Swift - 使用UIImagePickerController从相册选择照片并展示
- Excel单元格内容太多会覆盖遮住下一单元格范围
- 综述-如何克服HTML5的“性工能”障碍
- Perl入门(四)Perl的正則表達式
- Xamarin.forms 自定义dropdownview控件
- 枚举算法总结 coming~^.*
- uva 10069 Distinct Subsequences(高精度 + DP求解子串个数)