不错的题目!数论+背包dp,dp的时候附加计入一个个数就可以了~
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a) for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define SZ(a) ((int)a.size())
#define PP(n,m,a) puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb push_back
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 10011;
vector<int>p;
vector<int>vp;
bool isp[maxn];
int div(int x)
{
int temp = sqrt(x);
for(int i=1;i<p.size();i++)
{
if(x%p[i]==0)
{
return true;
}
if(p[i]>temp)
{
return false;
}
}
return false;
}
void init()
{
vp.clear();
p.clear();
MM(isp,false);
p.push_back(0);
p.push_back(2);
isp[2]=true;
for(int i=3;i<maxn;i++)
{
if(!div(i))
{
isp[i]=true;
p.push_back(i);
}
}
for(int i=1;i<p.size();i++)
{
if(isp[i])
{
vp.push_back(p[i]);
}
}
return ;
}
bool can[maxn];
int back[maxn];
int re[maxn];
void dpstart()
{
MM(can,false);
can[0]=true;
MM(back,0);
for(int i=0;i<maxn;i++)
{
re[i]=inf;
}
re[0]=0;
int now,temp;
for(int i=0;i<vp.size();i++)
{
now = vp[i];
for(int j=1;j<maxn;j++)
{
if(j-now>=0)
temp = re[j-now] + 1;
if( j-now>=0 && can[j-now] && temp < re[j])
{
can[j] = true;
back[j] = now;
re[j] = temp;
}
}
}
return ;
}
int n;
vector<int>v;
int main()
{
init();
dpstart();
cin>>n;
v.clear();
if(can[n])
{
int temp = n;
int now;
while(back[temp])
{
now = back[temp];
v.pb(now);
temp -= back[temp];
}
cout<<v.size()<<endl;
for(int i=0;i<v.size()-1;i++)
{
cout<<v[i]<<" ";
}
cout<<v.back()<<endl;
}
else
{
cout<<"0"<<endl;
}
return 0;
}
分享到:
相关推荐
SGU离线题库(2015-6-8整理),图片可以显示。。
SGU题库 Volume (100-199) pdf整合版
ID 标题 交流电 ... 116 超优质指数 2253 133 边界 2159 108 自我数字II 2149 144 会议 2121 175 编码方式 2032年 231 本金 2003年 134 质心 1931年 180 反演 1906年 106 等式 1884
sgu oj上的 101-121 的AC代码
SGU题库整合 Volume (200 - 299) pdf版
SGU-801综合通讯接入装置使用说明书
SGU-乌苏里奥斯日报 | | | | bre Sobre o projeto 最终开发基于Web的软件开发学科(2021年),以及由USUDo和UD CRUD com联合开发的Express,MongoDB数据库。 :rocket: 技术 :laptop: 安装,执行和分解 先决条件 ...
SGU推荐题目分类,适合初次使用sgu的编程爱好者使用!
SGU 390 AC源码,数位统计的难题
SGU 385,我写的程序,一道DP题,跟概率有关
辛苦整理所得,分略多,绝对值得,sgu完整题库(530个网页,还有试题难度排序)。lnddszp[at]gmail[dot]com
下载调度程序,用于低带宽环境。 全天扩展下载量
SGU 333 集训队AC程序,秒过,CPP
SGU 103AC 代码 质量有保证!
sgu ##这是一个将我的 sol 问题存储到 acm.sgu.ru 的存储库
“#babylonjs-sgu”
SGU Online Contester-具有模拟参加历史比赛的虚拟赛功能 http://acm.sgu.ru/ Codeforces-不断维护历届题库 http://codeforces.com 首先,要向读者介绍的是历史最悠久,最著名的OJ-西班牙Valladolid大学的...
pku sgu 经典图论题解答, 多种方法解答经典图论题, 附源代码
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.