鏈接：
官網(wǎng)：
http://118.190.20.162/view.page?gpid=T125
Acwing：https://www.acwing.com/problem/content/description/3417/

題意：順序給出數(shù)軸上N給不相等的點(diǎn)，記為序列a，首先將大區(qū)間[a[0],a[N-1]]劃分成若干個(gè)子區(qū)間[li,ri)，然后在子區(qū)間上面選取若干個(gè)點(diǎn)，要求這些點(diǎn)和區(qū)間端點(diǎn)構(gòu)成等差數(shù)列。端點(diǎn)不能作為選取的點(diǎn)。問(wèn)選取點(diǎn)的集合數(shù)量有多少。
分析：首先這是一個(gè)有限制的選擇問(wèn)題，我們見(jiàn)到的選擇問(wèn)題通常用dp、類dp、記憶化搜索來(lái)解決。dp和記憶化搜索的思想都是先把問(wèn)題分為多個(gè)階段的問(wèn)題，每一個(gè)階段都會(huì)對(duì)應(yīng)一個(gè)狀態(tài)，后面階段的狀態(tài)要利用已經(jīng)求出的狀態(tài)。
本題同理，首先求包含N個(gè)數(shù)的序列的方案數(shù)目這個(gè)問(wèn)題劃分階段，先求包含1個(gè)數(shù)序列的方案數(shù)，然后求包含2個(gè)數(shù)的…以以此類推，最后求出包含N個(gè)數(shù)的，就是最后的答案。
于是本題第i個(gè)狀態(tài)就是從第0個(gè)數(shù)第i個(gè)數(shù)的方案總數(shù),即dp[i]，一個(gè)維度就可以表示狀態(tài)
之后要看怎么用之前的階段求出各個(gè)階段的狀態(tài)值。對(duì)于第1個(gè)狀態(tài)，就是第0個(gè)數(shù)到第1個(gè)數(shù)的約數(shù)個(gè)數(shù)，對(duì)于第i個(gè)狀態(tài)，我們首先可以將第i個(gè)狀態(tài)這個(gè)大集合劃分成通過(guò)dp[i-1]求出的部分、通過(guò)dp[i-2]求出的部分…通過(guò)dp[0]求出的部分。比如在求通過(guò)第i-1個(gè)狀態(tài)即dp[i-1]求出的部分時(shí)，由于第i-1之前的方案取法不會(huì)影響i-1到i的取法，所以從0到i-1的取法有dp[i-1]種，而i-1到i的取法有a[i]-a[i-1]的約數(shù)個(gè)數(shù)個(gè)，設(shè)為cnt個(gè)，對(duì)于dp[i]的貢獻(xiàn)是cnt*dp[i-1]。
但是在求通過(guò)dp[i-2]求出的貢獻(xiàn)值時(shí)，i-2到i的方案會(huì)不會(huì)和i-1到i的方案重合？注意，現(xiàn)在要將dp[i]劃分成無(wú)交集，且并集為全集的子集，我們需要自己設(shè)計(jì)劃分方式。我們的方向是，能寫(xiě)出簡(jiǎn)單的dp[i]與dp[0…i-1]關(guān)系的式子。而我們已經(jīng)得到dp[i-1]的貢獻(xiàn)是dp[i-1]*cnt，我們希望能找到0到i-2的cnt。

最后我們發(fā)現(xiàn)如果i-2的cnt設(shè)置成包含i-2到i的約數(shù)，同時(shí)不含i-1到i的約數(shù)的集合的元素個(gè)數(shù)，我們就可以將問(wèn)題不重不漏的劃分。同時(shí)題目說(shuō)有障礙的地方不能種樹(shù)，所以i-2到i的方案本身就不會(huì)包含i-1到i的方案使用過(guò)的約數(shù)，因?yàn)閕-1到i的方案使用過(guò)的約數(shù)一定會(huì)經(jīng)過(guò)端點(diǎn)。
暴力找約數(shù)的方法

#include <iostream> #include<bits/stdc++.h> typedef long long ll; const int maxn=1000+5; const int mod=1000000000+7; const int maxa=100000+5; using namespace std; ll dp[maxn+5]; ll a[maxn+5]; vector<ll>v[maxa+10]; bool book[maxa+5]; ll solve(ll l,ll r){ll x=a[r]-a[l];ll cnt=0;if(x==1){//注意，相距為1不能種樹(shù)，而且之后約數(shù)1也不能再次使用，所以book[1]=1book[1]=1;return 0;}if(book[1]==0){book[1]=1;cnt++;//cout<<1<<"*"<<endl;}for(ll i=2;i*i<=x;i++){if(x%i==0){if(book[i]==0){book[i]=1;cnt++;}if(book[x/i]==0){book[x/i]=1;cnt++;}}}book[x]=1;//注意，x不能被第j-1之前的利用return cnt; } int main() {int N;cin>>N;for(int i=0;i<N;i++){scanf("%lld",&a[i]);}dp[0]=1;for(ll i=1;i<N;i++){memset(book,0,sizeof book);for(ll j=i-1;j>=0;j--){dp[i]=(dp[i]+dp[j]*solve(j,i))%mod;}}cout<<dp[N-1]<<endl;return 0; }

打表找約數(shù)

#include <iostream> #include<bits/stdc++.h> typedef long long ll; const int maxn=1000+5; const int mod=1000000000+7; const int maxa=100000+5; using namespace std; ll dp[maxn+5]; ll a[maxn+5]; vector<ll>v[maxa+10]; bool book[maxa+5]; int main() {for(int i=1;i<maxa;i++){//對(duì)于所有i的倍數(shù)，i都是他們的約數(shù)for(int j=2*i;j<maxa;j+=i){//從二倍開(kāi)始，可以排除約數(shù)為自己的情況，因?yàn)橛姓系K的地方不能種樹(shù)v[j].push_back(i);}}int N;cin>>N;for(int i=0;i<N;i++){scanf("%lld",&a[i]);}dp[0]=1;for(ll i=1;i<N;i++){memset(book,0,sizeof book);//每次對(duì)dp[i-1]的劃分操作對(duì)dp[i]的劃分操作沒(méi)有影響，要初始化標(biāo)記數(shù)組for(ll j=i-1;j>=0;j--){ll x=a[i]-a[j];ll cnt=0;for(int i=0;i<v[x].size();i++){if(book[v[x][i]]==0){//不能在障礙上種樹(shù)，對(duì)于第j-1個(gè)點(diǎn)a[j-1]來(lái)說(shuō)，a[i]-a[j]的約數(shù)的倍數(shù)是端點(diǎn),book[v[x][i]]=1;//端點(diǎn)是障礙，所以j-1前的約數(shù)都不能重復(fù)用cnt++;}}book[x]=1;//特別注意，雖然第j個(gè)端點(diǎn)不能cnt++，但是端點(diǎn)處不能種樹(shù)，他影響第j-1個(gè)端點(diǎn)使得其不能利用約數(shù)a[i]-a[j]dp[i]=(dp[i]+dp[j]*cnt)%mod;}}cout<<dp[N-1]<<endl;return 0; }

想試一試搜索，先是棧內(nèi)爆空間，然后改了set超時(shí)。。注意，這時(shí)候book不能開(kāi)全局了，因?yàn)槊總€(gè)狀態(tài)的計(jì)算是會(huì)交替進(jìn)行，而不是計(jì)算完一個(gè)再計(jì)算一個(gè)所以全局的book會(huì)亂套。

#include <iostream> #include<bits/stdc++.h> typedef long long ll; const int maxn=1000+5; const int mod=1000000000+7; const int maxa=100000+5; using namespace std; ll dp[maxn+5]; ll a[maxn+5]; vector<ll>v[maxa+10];ll N; ll dfs(ll level){if(level>=N-1){return 1;} // bool book[maxa+5]; // memset(book,0,sizeof book);//!!!!set<ll>book;for(ll i=level+1;i<N;i++){if(dp[i]==0){dp[i]=dfs(i);}ll cnt=0,x=a[i]-a[level];for(ll j=0;j<v[x].size();j++){if(find(book.begin(),book.end(),v[x][j])==book.end()){book.insert(v[x][j]);cnt++;}}book.insert(x);dp[level]=(dp[level]+dp[i]*cnt)%mod;// cout<<"$"<<dp[level]<<" "<<dp[i]<<" "<<cnt<<endl;}return dp[level]; } int main() {for(int i=1;i<maxa;i++){//對(duì)于所有i的倍數(shù)，i都是他們的約數(shù)for(int j=2*i;j<maxa;j+=i){//從二倍開(kāi)始，可以排除約數(shù)為自己的情況，因?yàn)橛姓系K的地方不能種樹(shù)v[j].push_back(i);}}cin>>N;for(ll i=0;i<N;i++){scanf("%lld",&a[i]);}dp[0]=dfs(0);cout<<dp[0]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的第22次CSP认证 第4题 校门外的树（3种方法，非常详细）（类dp+数学）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。