【历届试题 波动数列 】（01背包，滚动数组）

【历届试题 波动数列 】（01背包，滚动数组）

时间限制：1.0s 内存限制：256.0MB

问题描述

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3。

栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？

输入格式

输入的第一行包含四个整数 n s a b，含义如前面说述。

输出格式

输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。

样例输入

4 10 2 3

样例输出

2

样例说明

这两个数列分别是2 4 1 3和7 4 1 -2。

数据规模和约定

对于10%的数据，1<=n<=5，0<=s<=5，1<=a,b<=5；

对于30%的数据，1<=n<=30，0<=s<=30，1<=a,b<=30；

对于50%的数据，1<=n<=50，0<=s<=50，1<=a,b<=50；

对于70%的数据，1<=n<=100，0<=s<=500，1<=a, b<=50；

对于100%的数据，1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，1<=a, b<=1,000,000。

分析：比较容易写的是dfs 但是数据太大，只能得20分就T了

TLE【dfs】20分代码：

#include using namespace std;#define mem(a,n) memset(a,n,sizeof(a))#define memc(a,b) memcpy(a,b,sizeof(b))#define rep(i,a,n) for(int i=a;i=a;i--)///[n,a]#define pb push_back#define fi first#define se second#define IO ios::sync_with_stdio(false)#define fre freopen("in.txt","r",stdin)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long ll;typedef unsigned long long ull;const double PI=acos(-1.0);const double E=2.718281828459045;const double eps=1e-3;const int INF=0x3f3f3f3f;const int MOD=1e8+7;const int N=1e3+5;const ll maxn=1e6+5;const int dir[4][2]= {-1,0,1,0,0,-1,0,1};int n,s,a,b;int ans;void dfs(int sum,int cur,int cnt){ if(cnt==n) { if(sum==s) ans=(ans+1)%MOD; return ; } dfs(sum+cur+a,cur+a,cnt+1); dfs(sum+cur-b,cur-b,cnt+1);}int main(){ while(~scanf("%d%d%d%d",&n,&s,&a,&b)) { ans=0; for(int i=s-n*a;i<=s+n*b;i++) { dfs(i,i,1); } printf("%d\n",ans); } return 0;}

正解。。 dp， 但是也不能全过，可以得90分，最后一组数据T了，即使开挂也过不了

详解

TLE【01背包】90分代码：

#include using namespace std;#define mem(a,n) memset(a,n,sizeof(a))#define memc(a,b) memcpy(a,b,sizeof(b))#define rep(i,a,n) for(int i=a;i=a;i--)///[n,a]#define pb push_back#define fi first#define se second#define IO ios::sync_with_stdio(false)#define fre freopen("in.txt","r",stdin)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long ll;typedef unsigned long long ull;const double PI=acos(-1.0);const double E=2.718281828459045;const double eps=1e-3;const int INF=0x3f3f3f3f;const int MOD=1e8+7;const int N=1e3+5;const ll maxn=1e6+5;const int dir[4][2]= {-1,0,1,0,0,-1,0,1};ll n,s,a,b,f;ll dp[2][N*N];inline int Scan(){ int r = 0,f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { r = r * 10 + ch - '0'; ch = getchar(); } return r * f;}inline void Print(int x){ if(x<0) { x=-x; putchar('-'); } if(x>9) Print(x/10); putchar(x%10+'0');}void fun(){ f=0; dp[f][0]=1; for(ll i=1; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。