UVa 10520

UVa 10520【递推 搜索】-冯金伟博客园

哇!简直恶心的递推，生推了半天。。感觉题不难，但是恶心，不推出来又难受。。一不小心还A了[]~(￣▽￣)~*，AC的猝不及防。。。

先递推求出f[i][1](1<=i<=n-1),f[n][i](2<=i<=n)和f[i][j](2<=i<=n-1,1<=j<=i)，再递推一次求f[1][j](2<=j<=n),f[1][n]即为答案。其实不太肯定这样是否一定正确，因为我没有特别考虑j=0的边界情况，感觉好像也用不到这个情况。而且要用long long，刚开始用int会WA。

Reference Code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 ll f[30][30]={0};
 8 
 9 int main()
10 {
11     int n,an1;
12     while(scanf("%d%d",&n,&an1)==2)
13     {
14         memset(f,0,sizeof(f));
15         f[n][1]=an1;
16         for (int i=n-1;i>=1;i--){
17             f[i][1]=f[i+1][1]*2;
18         }
19         for(int i=2;i<=n;i++){
20             f[n][i]=f[n][i-1]*2;
21         }
22         for(int i=n-1;i>=2;i--){
23             for(int j=1;j<=i;j++){
24                 for(int k1=i+1;k1<=n;k1++){
25                     f[i][j]=max(f[i][j],f[k1][1]+f[k1][j]);
26                 }
27                 ll t=0;
28                 for(int k2=1;k2<j;k2++){
29                     t=max(t,f[i][k2]+f[n][k2]);
30                 }
31                 f[i][j]+=t;
32             }
33         }
34         for(int j=2;j<=n;j++){
35             for(int k=1;k<j;k++){
36                 f[1][j]=max(f[1][j],f[1][k]+f[k+1][j]);
37             }
38         }
39         cout<<f[1][n]<<endl;
40     }
41     return 0;
42 }

UVa 10520 递推

后来又看到了有人用深搜写，感觉其实好理解点而且不用想他们之间的递推关系，按照要求往下搜就好，省点脑子，比赛的时候适合这种写法。

Reference Code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 ll f[25][25]={0};
 8 ll n,a;
 9 
10 ll calc(int i,int j)
11 {
12     if(f[i][j]!=-1)
13         return f[i][j];
14     if(i<j){
15         ll Max=0;
16         for(int k=i;k<j;k++){
17             ll tmp=calc(i,k)+calc(k+1,j);
18             Max=max(Max,tmp);
19         }
20         return f[i][j]=Max;
21     }
22     ll Max1=0,Max2=0;
23     if(i<n){
24         for(int k=i+1;k<=n;k++){
25             ll tmp=calc(k,1)+calc(k,j);
26             Max1=max(Max1,tmp);
27         }
28     }
29     if(j>0){
30         for(int k=1;k<j;k++){
31             ll tmp=calc(i,k)+calc(n,k);
32             Max2=max(Max2,tmp);
33         }
34     }
35     return f[i][j]=Max1+Max2;
36 }
37 int main()
38 {
39     while(cin>>n>>a)
40     {
41         memset(f,-1,sizeof(f));
42         f[n][1]=a;
43         f[1][n]=calc(1,n);
44         cout<<f[1][n]<<endl;
45     }
46     return 0;
47 }

UVa 10520 深搜