P2750 贰五语言Two Five USACO5.5 记忆化搜索
正解:记搜+逼近
解题报告:
神仙题预警,,,
我真滴觉得还是挺难的了,,,
大概说下思路趴QAQ
首先我们要知道逼近法是什么!
逼近法,有点像二分的思路,以这题为例举个eg
假如它给了个数字k.我们现在要求b是在(1,2)还是在(2,1)
显然所有b在(1,2)时候的字符串都在(2,1)的前边,且中间没有其他可能排列了
辣我们就先把b放在(1,2)算出这时候的方案数是多少
如果这时候方案数>k,说明b就是在(1,2)
否则在(2,1)
欧克get了趴?
然后知道这个之后,就,说下怎么求方案数呢?
这里我们要用到,轮廓线
显然当我们从小到大填的时候,如果在某一格填入了一个数,它的左上一定都填完了,所以可以发现它形成的轮廓线一定长度递减
然后我们可以用dp递推一下(也可以说是用记搜,,,但我一直jio得记搜属于dp鸭?
大力转移一波就可以得到方案数辣!
overr!
很妙啊我真的觉得!
所以代码大概是下午写QwQ
#include<bits/stdc++.h> using namespace std; #define ll int #define rp(i,x,y) for(register ll i=x;i<=y;++i) ll f[6][6][6][6][6],s[30],ans;//si:第i个位置的字母是什么 bool qd[30];//qdi:第i个字母确定了没有 inline ll read() { register char ch=getchar();register ll x=0;register bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } inline bool check(ll lt,ll wz){return (!s[wz] || lt==s[wz]);} ll dfs(ll a,ll b,ll c,ll d,ll e) { ll lt=a+b+c+d+e+1; //lt:在确定哪个 if(lt>25) return 1;if(f[a][b][c][d][e]!=0)return f[a][b][c][d][e]; if(a<5 && check(lt,a+1))f[a][b][c][d][e]+=dfs(a+1,b,c,d,e); if(b<a && check(lt,b+6))f[a][b][c][d][e]+=dfs(a,b+1,c,d,e); if(c<b && check(lt,c+11))f[a][b][c][d][e]+=dfs(a,b,c+1,d,e); if(d<c && check(lt,d+16))f[a][b][c][d][e]+=dfs(a,b,c,d+1,e); if(e<d && check(lt,e+21))f[a][b][c][d][e]+=dfs(a,b,c,d,e+1); return f[a][b][c][d][e]; } void wk1(ll num) { rp(i,1,25) { for(s[i]=1;;++s[i]) { if(qd[s[i]])continue;qd[s[i]]=1;memset(f,0,sizeof(f)); int tmp=dfs(0,0,0,0,0);if(ans+tmp>=num)break;ans+=tmp;qd[s[i]]=0; } } rp(i,1,25)cout<<char(s[i]+'A'-1); } void wk2() { string str;cin>>str; ans=0; rp(i,0,24) { for(s[i+1]=1;s[i+1]<=str[i]-'A';s[i+1]++) { if(qd[s[i+1]])continue;qd[s[i+1]]=1;memset(f,0,sizeof(f)); ans+=dfs(1,0,0,0,0);qd[s[i+1]]=0; } } cout<<ans+1<<endl; } int main () { char opt;cin>>opt; if(opt=='N')wk1(read()); else wk2(); return 0; }