hdu 2189还是dp..
2024-09-05 05:30:23
题目的意思比较简单,类似计数dp。
一开始我想让dp[i]+=dp[i-prime] 每次遍历比i小的所有素数,然后发现有重叠的 比如 2+3 3+2
就导致错误。看了其他人的填充方式,发现定下prime 然后定向的更新i就可以避免重复问题
还有就是。。 尼玛的素数筛法居然 居然。。写错了。。 反省一个小时。。
贴上丑陋的代码。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;//利用一个二分定位
int myprime[];
void get_prime()// 小小的素数筛法
{
int vis[];
memset(vis,,sizeof(vis));
int ret=;
vis[]=vis[]=;
for(int i=;i<=;i++)
{
if(vis[i]==)
{
myprime[++ret]=i;
int j;
for(j=i+i;j<=;j+=i) vis[j]=;//为1表示不是prime
}
}
}
int main()
{
//cin.sync_with(false);
int dp[];
int t;
cin>>t;
get_prime();
while(t--)
{
int n;
cin>>n;
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=;i++)
{
for(int j=myprime[i];j<=n;j++) dp[j]+=dp[j-myprime[i]];
}
cout<<dp[n]<<endl;
}
return;
}
最新文章
- iOS之清除缓存
- ios数据永久存储之----NSUserDefaults
- 第一天 Linux 是什么
- Yii提供的Htmler助手checkboxList可自定义Checkbox输出格式
- 利用Xilinx中的ROM构造查找表来计算sin和cos的方法探讨
- EventUtil.addHandler方法
- kbengine_js_plugins 在Cocos Creator中适配
- 在实际项目中使用LiteDB NoSQL数据库
- java连接mysql以及增删改查操作
- Spring3 MVC
- 搭建springboot环境
- 浙江省赛 ZOJ4029
- ASP.NET MVC 的常用的HTML辅助方法笔记
- 2016/4/14腾讯Android实习面试
- 将Ext JS 5应用程序导入Web项目中
- C#中【正则表达式regular expression】相关的知识
- 关于HashTable,HashMap和TreeMap的几点心得
- ubuntu 配置tomcat 实测成功
- 苹果终端wifi图标点亮慢和portal弹窗机制分析以及处理办法和建议
- Javascript-- jQuery DOM篇(二)
热门文章
- Mybatis 传入多个参数查询数据 (3种方法)
- 重读APUE(15)-pthread_cond_wait与while循环
- matplotlib画图报错This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
- mongoose 建立schema 和model
- js中的splice方法和slice方法简单总结
- opencv_traincascade级联训练人脸数据
- 如何用CSS3来实现卡片的翻转特效
- Ubuntu 18.04设置1920*1080
- JS_&;&;||
- 如何设置payjs的微信jsapi支付目录