【做题笔记】洛谷P1036 选数
2024-09-06 22:18:17
作为一个 DFS 初学者这题真的做得很惨。。。其实窝学 DFS 一年多了,然后一开始就学不会最近被图论和数据结构打自闭后才准备好好学一学233
一开始,直接套框架,于是就有
#include <iostream>
#include <stdio.h>
using namespace std;
int n,k,a[21],ans,sum,book[50000010];
int pd(int x)
{
for(int i=2;i<x;i++)
if(!(x%i))
return 0;
return 1;
}
void dfs(int f)
{
if((f==k)&&pd(sum))
{
++ans;
return ;
}
for(int i=1;i<=n;i++)
{
if(!book[i])
{
sum+=a[i];
book[i]=1;
dfs(f+1);
book[i]=0;
sum-=a[i];
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(0);
printf("%d\n",ans);
return 0;
}
在,为什么过不了样例?
然后猛然想起会有重复的算式。比如 1+2+3
在这题中和 1+3+2
是一样的
似乎没啥好办法。
然后猛然想起 cdcq 大佬以前似乎讲过一种“升序排列”的方法
具体叫啥窝也不记得了。。不过注意,这里不是说按照数值升序排列,而是按照下标。即,现找到下标为 1 ,然后一个一个往后退。比如拿样例来说:
4 3
3 7 12 19
按下标升序排列就是
3 7 12
3 7 19
3 12 19
7 12 19
也就是每次选择当前排列最末一个数在原序列位置后的一个数
于是就很喜闻乐见的 AC 了
#include <iostream>
#include <stdio.h>
using namespace std;
int n,k,a[21],ans,book[50000010];
int pd(int x)
{
for(int i=2;i<x;i++)
if(!(x%i))
return 0;
return 1;
}
void dfs(int f,int sum,int now)
{
if((f==k)&&pd(sum))
{
++ans;
return ;
}
for(int i=now;i<=n;i++)
dfs(f+1,sum+a[i],i+1);
return ; //搞完全部就退出
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(0,0,1);
printf("%d\n",ans);
return 0;
}
最新文章
- ThinkPHP 整合Bootstrap Ajax分页
- [转]UE4 Blueprint编译过程
- [源码]String StringBuffer StringBudlider(1String部分)
- 使用NVelocity生成内容的几种方式
- 500 OOPS: vsftpd: both local and anonymous access
- JAVA基础学习之XMLCDATA区、XML处理指令、XML约束概述、JavaBean、XML解析(8)
- Spring IOC容器中注入bean
- deepdetect 用c++11写的机器学习caffe和XGBoost API 接口
- mysql启动不起来了!
- [置顶] 深入浅出Spring(一)Spring概述
- VS013的单元测试去哪里了
- vim highlight whitespace at end of line and auto delete them
- Unity渲染优化中文翻译(二)——CPU的优化策略
- java程序员--小心你代码中的内存泄漏
- 1.Nginx服务应用
- MySQL事务以及隔离级别
- event 和delegate的分别
- 第四章:4.0 python常用的模块
- Rocketlab公司火箭Electron介绍
- vue源码逐行注释分析+40多m的vue源码程序流程图思维导图 (diff部分待后续更新)
热门文章
- P1282 多米诺骨牌【dp】
- Wannafly Winter Camp 2020 Day 5G Cryptographically Secure Pseudorandom Number Generator - 分块
- 04、extern引用全局变量
- gcc,g++,make,cmake的区别
- vue加载单文件使用vue-loader报错
- solr 对于 关键字的特殊处理
- 第一次个人编程作业&;#183;寒假
- HTML-表格-基础表格
- Selenium(Webdriver)自动化测试常问问题
- 2019牛客竞赛第六场D Move 宏观单调,部分不单调