UVA 10564 Paths through the Hourglass DP-白红宇

UVA 10564 Paths through the Hourglass DP

阅读量：5963 次

发布时间：2019-06-19

本文共 2014 字，大约阅读时间需要 6 分钟。

注意用long long。

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;typedef long long ll;typedef pair
                    
                      pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template
                     
                       T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template
                      
                        T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}void debug() {#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}int n,s;int da[50][50];ll dp[50][50][550];ll f(int k,int pos,int s){ if(dp[k][pos][s]>=0)return dp[k][pos][s]; if(k==2*n-1)return dp[k][pos][s]=s==da[k][pos]?1:0; ll x=0; if(k
                       
                        =da[k][pos])x+=f(k+1,pos-1,s-da[k][pos]); if(pos!=abs(k-n)+1&&s>=da[k][pos])x+=f(k+1,pos,s-da[k][pos]); }else { if(s>=da[k][pos])x+=f(k+1,pos,s-da[k][pos]); if(s>=da[k][pos])x+=f(k+1,pos+1,s-da[k][pos]); } return dp[k][pos][s]=x;}int main(){ // freopen("d:\\in.txt","r",stdin); while(scanf("%d%d",&n,&s)!=EOF&&(n||s)) { for(int i=1;i<=2*n-1;i++) { for(int j=1;j<=abs(i-n)+1;j++) scanf("%d",&da[i][j]); } ll num=0; memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++) { num+=f(1,i,s); } printf("%lld\n",num); if(num==0) printf("\n"); else { for(int i=1;i<=n;i++)if(dp[1][i][s]>0) { printf("%d ",i-1); int pos=i; int ns=s; for(int k=1;k<2*n-1;k++) { if(k
                        
                         0) { printf("L"); ns-=da[k][pos];--pos; }else { printf("R"); ns-=da[k][pos]; } }else { if(dp[k+1][pos][ns-da[k][pos]]>0) { printf("L"); ns-=da[k][pos]; }else { printf("R"); ns-=da[k][pos];pos++; } } } break; } printf("\n"); } } return 0;}