一道区间dp题，通过分析我们可以得知，跳完len步，此时覆盖的区间是连续的，所以有左端点和右端点，设置f [ i ] [ j ] 为 此 时 跳 到 某 一 步 左 端 点 为 i ， 右 端 点 为 j 的 最 高 分 f[i][j]为此时跳到某一步左端点为i，右端点为j的最高分f[i][j]为此时跳到某一步左端点为i，右端点为j的最高分，那他们怎么转移过来呢？，左端点由左端点右边的最近的没有走过点转移过来，右端点由左边的最近的没有走过的点转移过来。所以动态转移式为：
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] + a [ i ] ∗ l e n , f [ i ] [ j − 1 ] + a [ j ] ∗ l e n ) f[i][j]=max(f[i+1][j]+a[i]*len,f[i][j-1]+a[j]*len)f[i][j]=max(f[i+1][j]+a[i]∗len,f[i][j−1]+a[j]∗len)
还要注意是环，常见的处理方式是开两倍数组。
#include<bits/stdc++.h> using namespace std; const int N=2100; int n,a[N*2]; typedef long long ll; ll f[N*2][N*2]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; f[i][i]=a[i]; f[i+n][i+n]=a[i+n]; } for(int len=2;len<=n;len++) { for(int i=1;i<=n*2-len+1;i++) { int j=i+len-1; f[i][j]=max(f[i+1][j]+1LL*a[i]*len,f[i][j-1]+1LL*a[j]*len); } } ll ans=0; for(int i=1;i<=n;i++) { ans=max(ans,f[i][i+n-1]); } cout<<ans<<endl; return 0; }
题目要求最长公共子串长度大于k，那么可以转化一下，改为存在长度为k的公共子串
因为字符串长度小于10，可以直接枚举x,y，然后求所有长为k的子串，用个数组存下来求匹配
时间复杂度 n 2 l o g n n^2lognn2logn
#include<bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define pb push_back const int N = 2005, INF = 0x3f3f3f3f; ll qpow(int a, int b) {ll ans = 1; while (b) {if (b & 1) ans = ans * a;a = a * a;b >>= 1;}return ans;} int ans=0; int n,k; int hs[200005]; int a[N]; void insert(int x) { int cnt=0; while(x) { a[++cnt]=x&1; x>>=1; } int now=0; for(int i=1;i<=k;i++) { now=now*2+a[i]; } hs[now]=1; for(int i=k+1;i<=cnt;i++) { now=(now-(1ll<<(k-1))*a[i-k])*2+a[i]; hs[now]=1; } return; } void query(int x) { int cnt=0; while(x) { a[++cnt]=x&1; x>>=1; } int now=0; for(int i=1;i<=k;i++) { now=now*2+a[i]; } if(hs[now]) { ans++; return; } for(int i=k+1;i<=cnt;i++) { now=(now-(1ll<<(k-1))*a[i-k])*2+a[i]; if(hs[now]) { ans++; return; } } return; } void clear(int x) { int cnt=0; while(x) { a[++cnt]=x&1; x>>=1; } int now=0; for(int i=1;i<=k;i++) { now=now*2+a[i]; } hs[now]=0; for(int i=k+1;i<=cnt;i++) { now=(now-(1ll<<(k-1))*a[i-k])*2+a[i]; hs[now]=0; } return ; } void solve() { cin>>n>>k; ans=0; for(int i=1;i<=n;i++) { int w1=log2(i)+1; if(w1<k) continue; insert(i); for(int j=i+1;j<=n;j++) { int w2=log2(j)+1; if(w2<k) continue; query(j); } clear(i); } cout<<ans<<endl; } int main() { ios::sync_with_stdio; cin.tie(0);cout.tie(0); int T=1; //cin>>T; while(T--) { solve(); } return 0; }
dp题，bfs也可以过，如果此时的a[i]为负数，回到左边时间会增加，对答案是没有贡献的，当a[i]>0时，
状态转移为:f [ i + j ] = m i n ( f [ i + j ] , f [ i ] + 1 ) ; f[i+j]=min(f[i+j],f[i]+1);f[i+j]=min(f[i+j],f[i]+1);
代码如下:
#include<bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define pb push_back const int N = 1e6, INF = 0x3f3f3f3f; ll qpow(int a, int b) {ll ans = 1; while (b) {if (b & 1) ans = ans * a;a = a * a;b >>= 1;}return ans;} int n; int a[N]; int f[N]; int now; void solve() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,0x3f,sizeof f); f[1]=0; for(int i=1;i<n;i++) { if(a[i]>0) for(int j=1;j<=a[i];j++) { f[i+j]=min(f[i+j],f[i]+1); } } if(f[n]!=0x3f3f3f3f) cout<<f[n]<<endl; else cout<<-1<<endl; } int main() { ios::sync_with_stdio; cin.tie(0);cout.tie(0); int T=1; //cin>>T; while(T--) { solve(); } return 0; }
如何判断一个数xxx能不能选出若干数使得gcd=xgcd=xgcd=x
首先选出来的数一定是xxx的倍数（显然）
然后要让集合gcd是xxx,那么显然是xxx倍数的a[i]a[i]a[i]全部都选才越有可能是xxx，（因为是一路取gcd）
所以枚举xxx（不一定要出现过）,然后在枚举它的倍数,如果出现过就和已选的取个g c d gcdgcd
是个调和级数
时间复杂度o ( n l o g l o g n ) o(nloglogn)o(nloglogn)
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int st[N]; int ok[N]; int n,m,t; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) st[i]=ok[i]=0; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); st[x]=1; } for(int i=1;i<=n;i++) { for(int j=1;j*i<=n;j++) { if(st[i*j]) { ok[i]=gcd(ok[i],i*j); } } } while(m--) { int x; scanf("%d",&x); if(ok[x]==x) cout<<"YES\n"; else cout<<"NO\n"; } } return 0; }
这次小白月赛题目难度不是很大至此，就全部补完啦！
