記憶搜索

簡單題解： 剛看到這題的時候，毫無頭緒。 看了NOCOW上的題解才恍然大悟。 這題卡了我4天。 蛋疼的是，第二天的時候我已經改對了，但是將輸出與樣例比對時坑爹了.... ? 矩陣轉編號： 如矩陣ACEGI...... 只需求出以AB、ACD、ACEF、ACEFH......開頭的矩陣的數目之和再加1即可。 編號轉矩陣： 順次枚舉每一位，若當前方案開頭的矩陣數目小于n則減去，否則即可確定當前位。 ? 如何求以固定串開頭的矩陣數目呢？ 記憶化搜索！ 令f[a][b][c][d][e]表示各行分別放入了a,b,c,d,e個字符的方案數。 則合法狀態中，必然五參數不嚴格遞減。 從小往大枚舉每一字符，選擇放到哪一行中，且必然放在該行接下來的一格中。 ?

原博客地址

/*
ID: jinbo wu
LANG:C++
TASK:twofive
*/
#include<bits/stdc++.h>
using namespace std;
char  ss[33],s[33];
int n;
int f[6][6][6][6][6];
bool ok(int h,int  now)
{return (!s[h]||s[h]==now+'A');}
int dfs(int a,int b,int c,int d,int e,int now)
{if(now>=25)return 1;int res=f[a][b][c][d][e];if(res)return res;if(a<5&&ok(a,now)) res+=dfs(a+1,b,c,d,e,now+1);if(b<a&&ok(b+5,now)) res+=dfs(a,b+1,c,d,e,now+1);if(c<b&&ok(c+10,now)) res+=dfs(a,b,c+1,d,e,now+1);if(d<c&&ok(d+15,now)) res+=dfs(a,b,c,d+1,e,now+1);if(e<d&&ok(e+20,now)) res+=dfs(a,b,c,d,e+1,now+1);return f[a][b][c][d][e]=res;
}
int main()
{freopen("twofive.in","r",stdin);freopen("twofive.out","w",stdout);char c;while(cin>>c){if(c=='N'){cin>>n;for(int i=0;i<25;i++){for(s[i]='A';;s[i]++){memset(f,0,sizeof(f));int tmp=dfs(0,0,0,0,0,0);if(tmp>=n)break;n-=tmp;}}cout<<s<<endl;}else{cin>>ss;int ans=0;for(int i=0;i<25;i++){for(s[i]='A';s[i]<ss[i];s[i]++){memset(f,0,sizeof(f));ans+=dfs(0,0,0,0,0,0);}//cout<<ans<<endl;}cout<<ans+1<<endl;}}
}

總結

以上是生活随笔為你收集整理的twofive（记忆搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。