首页 > 代码库 > topcoder srm 687 div1
topcoder srm 687 div1
1、$A_{1}=2,A_{2}=3,A_{n}=A_{n-2}+A_{n-1}-1$。给出数字$n$，将其表示成若干个$A$中的不同元素的和。
思路：设$B_{n}=A_{n}-1$，那么有$B_{n}=B_{n-2}+B_{n-1},B_{1}=1,B_{2}=2$。那么$B$其实是斐波那契数列。设将$n$表示成$k$个$A$中的元素，那么就等同于将$n-k$表示成$k$个$B$中不同的元素。这个分两步进行：（1）将$n-k$表示成最少的$B$中元素的和，（2）如果这个个数大于$k$那么无解。若小于$k$，可以将某个数字$x=B_{t}$替换为$B_{t-2}+B_{t-1}$以增加一个数字。
#include <stdio.h>#include <string.h>#include <string>#include <iostream>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <stack>using namespace std;long long f[100];int n;void init(long long x){ f[1]=1; f[2]=2; for(int i=3;i<100;++i) { f[i]=f[i-1]+f[i-2]; if(f[i]>x) { n=i-1; break; } }}vector<int> ans;int check(int k,long long x){ if(x<=0) return 0; ans.clear(); while(x>0) { for(int i=n;i>=1;--i) if(x>=f[i]) { ans.push_back(i); x-=f[i]; break; } } if((int)ans.size()>k) return 0; while((int)ans.size()<k) { sort(ans.begin(),ans.end()); int ok=0; for(int i=0;i<(int)ans.size();++i) { if((i==0&&ans[0]>=3)||(i!=0&&ans[i]-ans[i-1]>=3)) { ans.push_back(ans[i]-1); ans[i]-=2; ok=1; break; } } if(!ok) return 0; } return 1;}class AlmostFibonacciKnapsack{public: vector<int> getIndices(long long x) { init(x); for(int i=1;i<=n;++i) if(check(i,x-i)) return ans; return vector<int>{-1}; }};
topcoder srm 687 div1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。