数据范围：p,q≤20。
只能说我整个人傻逼了.....
我们考虑三角函数的部分性质：
$sin(x)=\sqrt{ 1-cos^2(x)}$
$cos(x)=\sqrt{1-sin^2(x)}$
$tan(x)=\frac{sin(x)}{cos(x)}$
根据这三条公式，我们可以据此推出以下六种转移方式，即：
$arcsin(x)→cos(x)\ or\ tan(x)$
$arccos(x)→sin(x)\ or\ tan(x)$
$arctan(x)→sin(x)\ or\ cos(x)$
我们又根据上述的部分性质，我们用分数$\frac{\sqrt{a}}{\sqrt{b}}$去表示x，其中a,b均为非负整数。
不难根据以下转移式子得到转移出的根式
由$arcsin(x)→cos(x)$得到$\frac{\sqrt{b-a}}{\sqrt{b}}$
由$arcsin(x)→tan(x)$得到$\frac{\sqrt{a}}{\sqrt{b-a}}$
由$arccos(x)→sin(x)$得到$\frac{\sqrt{b-a}}{\sqrt{b}}$
由$arccos(x)→tan(x)$得到$\frac{\sqrt{b-a}}{\sqrt{a}}$
由$arctan(x)→sin(x)$得到$\frac{\sqrt{a}}{\sqrt{a+b}}$
由$arctan(x)→cos(x)$得到$\frac{\sqrt{b}}{\sqrt{a+b}}$
然后简单地记忆搜索以下就可以了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int vis[805][805]={0}; 4 int x,y; 5 int cnt[2505]={0}; int use=0; 6 void add(int x,int y){cnt[++use]=y; cnt[++use]=x;} 7 int dfs(int a,int b){ 8 if(a>800||b>800||a<0||b<=0||(a==0&&b!=1)) return 0; 9 int d=__gcd(a,b); 10 a/=d; b/=d; 11 if(a==x&&b==y) return 1; 12 if(vis[a][b]) return 0; 13 vis[a][b]=1; 14 if(dfs(b-a,b)) {add(2,3); return 1;} 15 if(dfs(a,b-a)) {add(2,5); return 1;} 16 if(dfs(a,a+b)) {add(6,1); return 1;} 17 if(dfs(b,a+b)) {add(6,3); return 1;} 18 if(dfs(b-a,b)) {add(4,1); return 1;} 19 if(dfs(b-a,a)) {add(4,6); return 1;} 20 return 0; 21 } 22 23 int main(){ 24 string s; cin>>s; 25 scanf("%d/%d",&x,&y); 26 int d=__gcd(x,y); 27 x/=d; y/=d; 28 x=x*x; y=y*y; 29 dfs(0,1); 30 while(use--){ 31 printf("%d",cnt[use+1]); 32 } 33 }