Uva 10192&10066-（DP） - c++编程基础

题目链接：点击打开链接点击打开链接

两道都是LCS。。裸水过

10192：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 1005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair
               
                 #define ull unsigned long long using namespace std; short dp[200][200]; char s[200],t[200]; int cas=1; void solve() { memset(dp,0,sizeof(dp)); int lens=strlen(s),lent=strlen(t); for(int i=1;i<=lens;i++) for(int j=1;j<=lent;j++) if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); printf("Case #%d: you can visit at most %d cities.\n",cas++,dp[lens][lent]); } int main() { while(gets(s)&&s[0]!='#') { gets(t); solve(); } return 0; }

10066：注意每组数据间有个空行。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 1005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair
               
                 #define ull unsigned long long using namespace std; short dp[102][102]; int s[102],t[102]; int cas=1,lens,lent; void solve() { memset(dp,0,sizeof(dp)); for(int i=1;i<=lens;i++) for(int j=1;j<=lent;j++) if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); printf("Twin Towers #%d\nNumber of Tiles : %d\n",cas++,dp[lens][lent]); puts(""); } int main() { while(scanf("%d%d",&lens,&lent)) { if(!lens&&!lent)break; for(int i=1;i<=lens;i++) scanf("%d",s+i); for(int i=1;i<=lent;i++) scanf("%d",t+i); solve(); } return 0; }