波动数列--蓝桥杯(hard)
这道题不爆0就是大成功 ,苦笑.jpg
https://www.acwing.com/problem/content/1216/
三个方法的通过得分(总分25):
- 10
- 20
- 25
1.枚举首项,dfs暴搜 (medium)
根据特例推演出首部可能的上界与下界。以减少枚举首部的清况;
dfs函数设计:
param1:int x 上一个的序列值
param2:int cnt 路径上的个数
param3:int sum 路径上序列值的和
分支设计:
dfs(x+a,cnt+1,sum+x+a);
dfs(x-b,cnt+1,sum+x-b);
#include <bits/stdc++.h>
using namespace std;
const int MOD =1e8 +7;
const int N = 1010;
int n,s,a,b;
int ans;
//枚举首项+dfs
vector<int> path;
void dfs(int x,int cnt ,int sum){
if(cnt==n){
if(sum==s){
//for(int i=0;i<n;i++) cout<<path[i]<<" ";
//puts("");
ans++;
}
if(ans>MOD) ans%=MOD;
return ;
}
path.push_back(x+a);
dfs(x+a,cnt+1,sum+x+a);
path.erase(path.end()-1);
path.push_back(x-b);
dfs(x-b,cnt+1,sum+x-b);
path.erase(path.end()-1);
}
int main(){
cin>>n>>s>>a>>b;
int x1=(s -a*n*(n-1)/2)/n;
int x2=(s +b*n*(n-1)/2)/n;
for(int i=x1;i<=x2;i++){
//清空path
path.clear();
path.push_back(i);
dfs(i,1,i);
}
cout<<ans;
//cout<<path.size();
return 0;
}
2.对第一种情况进行优化 (hard)
+a -b 的操作总和 总为 n(n-1)/2 ,可以再次减少i 的枚举次数
先固定 a的区间来枚举,自然得出b的值, 先进行一次 判定
n*i+ta*a-tb*b==s
#include <stdc++.h>
using namespace std;
const int MOD =1e8 +7;
const int N = 1010;
int n,s,a,b;
int ans;
//枚举首项+dfs
vector<int> path;
void dfs(int x,int cnt ,int sum){
if(cnt==n){
if(sum==s){
for(int i=0;i<n;i++) cout<<path[i]<<" ";
puts("");
ans++;
}
if(ans>MOD) ans%=MOD;
return ;
}
path.push_back(x+a);
dfs(x+a,cnt+1,sum+x+a);
path.erase(path.end()-1);
path.push_back(x-b);
dfs(x-b,cnt+1,sum+x-b);
path.erase(path.end()-1);
}
int main(){
cin>>n>>s>>a>>b;
int x1=(s -a*n*(n-1)/2)/n;
int x2=(s +b*n*(n-1)/2)/n;
for(int i=x1;i<=x2;i++){ //ta+tb=n*(n-1)/2 为+a -b操作数之和
for(int ta=0;ta<=n*(n-1)/2;ta++){
int tb=n*(n-1)/2 -ta;
if(n*i+ta*a-tb*b==s){
//清空path
path.clear();
path.push_back(i);
dfs(i,1,i);
}
}
}
cout<<ans;
//cout<<path.size();
return 0;
}
3.在2方法上进一步优化,转换为0-1背包问题。(so hard)待续。。。