1001：求最大子段和，关键是判断当前位置选与不选的状态状态转移方程：dp[i]=max(dp[i-1]+a[i],a[i]);还要记录起点与终点（单独开了一个结构体记录到达每个点的起点与终点）

1 #include 
      
         2 #include 
       
          3 int dp[100007],a[100007];  4 struct node  5 {
     6     int s,e;  7 }p[100007];  8 int main()  9 {
    10     int t,n,cas=1,i; 11     scanf("%d",&t); 12     while(t--) 13     {
    14         memset(dp,0,sizeof(dp)); 15         scanf("%d",&n); 16         printf("Case %d:\n",cas++); 17         for(i=0;i
        
         =a[i]) 24             {
    25                 dp[i]=dp[i-1]+a[i]; 26                 p[i].s=p[i-1].s; 27                 p[i].e=i; 28             } 29             else 30             {
    31                 dp[i]=a[i]; 32                 p[i].s=i; 33                 p[i].e=i; 34             } 35         } 36         int max=dp[0]; 37         int tx=0; 38         for(i=1;i
         
          max) 41             {
    42                 max=dp[i]; 43                 tx=i; 44             } 45         } 46         printf("%d %d %d\n",max,p[tx].s+1,p[tx].e+1); 47         if(t>0) 48         printf("\n"); 49     } 50     return 0; 51 }
         
        
       
      

1002：也是一个求最大子段和的问题，不过就是把二维的转化成一维的数组然后按照一维最大子段和，最后找出最大的。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 int sum[107],f[107][107];  5 int n;  6 int get_s(int dp[])  7 {
     8     int i;  9     for(i=1;i
         
          dp[i]) 12         dp[i]=dp[i-1]+dp[i]; 13     } 14     int max=dp[0]; 15     for(i=1;i
         
        
       
      

1003 原来做过的一题目，LCIS求最长上升子序列o(n^2)超时，要用o(nlogn)的方（二分查找）法,虽然明白了了，但是细节上还是出了很多错误。。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 using namespace std;  6 const int max_s = 500007;  7 int a[max_s],len[max_s];  8 int B_search(int num,int l,int r)  9 {
    10     while(l<=r) 11     {
    12         int m=(l+r)>>1; 13         if(len[m]>num) r=m-1; 14         else if(len[m]
          
           len[k]) 45             {
    46                 len[++k]=a[i]; 47             } 48             else 49             {
    50                 int pos=B_search(a[i],1,k); 51                 len[pos]=a[i]; 52             } 53         } 54         if(k==1) 55         printf("My king, at most %d road can be built.\n\n",k); 56         else 57         printf("My king, at most %d roads can be built.\n\n",k); 58     } 59     return 0; 60 }
          
         
        
       
      

1004：才开始以为直接打表推出来然后排序就可以，结果我悲催了，这样算的中间过程会出现超出（—int64\long lng ）的范围的数据，最后还是要应该是每次选出最小的来加到数组里面的：

f[i]=min(l1*2,l2*3,l3*5,l4*7);

选出来最小的以后对四个只里面等于（这里很重要）min的L要++，这样选出来的就不会超数据，了而且还不用排序，还有英语，MD悲剧啊。。很多都不会啊。。

11---19；单独拿出来＋ｔｈ其他的１＋st.2+nd,3+rd 其他加th主要的区别在两位数上，三位以上就直接按两位处理，面临这样的英语实在蛋疼啊。。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 const int max_s = 58508;  6 __int64 f[max_s];  7 int len;  8 int l1,l2,l3,l4;  9 void Min(__int64 a,__int64 b,__int64 c,__int64 d) 10 {
    11     __int64 m=20000000001; 12     if(m>a) m=a; 13     if(m>b) m=b; 14     if(m>c) m=c; 15     if(m>d) m=d; 16     f[++len]=m; 17    if(m==a) l1++; 18    if(m==b) l2++; 19    if(m==c) l3++; 20    if(m==d) l4++; 21 22 } 23 void init() 24 {
    25     len=1; 26     f[1]=1; 27     l1=l2=l3=l4=1; 28     while(len<=5842) 29     {
    30       Min(f[l1]*2,f[l2]*3,f[l3]*5,f[l4]*7); 31     } 32     /*for(int i=1;i<=5842;i++) 33     printf("%I64d ",f[i]); 34     printf("\n");*/ 35 } 36 int main() 37 {
    38     int n; 39     init(); 40     while(scanf("%d",&n),n) 41     {
    42        if((n%100)/10!=1) 43        {
    44            if(n%10==1) 45            printf("The %dst humble number is %I64d.\n",n,f[n]); 46            else if(n%10==2) 47            printf("The %dnd humble number is %I64d.\n",n,f[n]); 48            else if(n%10==3) 49            printf("The %drd humble number is %I64d.\n",n,f[n]); 50            else 51            printf("The %dth humble number is %I64d.\n",n,f[n]); 52        } 53        else 54        {
    55             printf("The %dth humble number is %I64d.\n",n,f[n]); 56        } 57     } 58     return 0; 59 }
        
       
      

1005 以前没大接触过LCS，看了看《算法导论》，隐约明白了，可是做起这道题来，还是很费劲，我是看的结题报告（鄙视我吧）

将题目转化成算法导论上的那个矩阵：

首先将s1,s2转换到a,b里面这样方便处理，并且把,0,0位置空出来了，

f[i][j]=max(f[i-1][j-1]+map[a[i]][b[j]],f[i-1][j]+map[a[i]][4],f[i][j-1]+map[4][b[j]]);

  1.s1取第i个字母，s2取“-”：f[i-1,j] + map[s1[i],'-']

  2.s1取“-”，s2取第j个字母：f[i,j-1] + map['-',s2[j]]

  3.s1取第i个字母，s2取第j个字母：f[i-1,j-1] + map[s1[i],s2[j]]

  即f[i,j] = max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + smap['-',s2[j]], f[i-1,j-1] + map[s1[i],s2[j]]);

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 using namespace std;  5 int map[5][5]={
     {
     5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},{-1,-2,-2,5,-1},{ -3,-4,-2,-1,0}};  6 int a[107],b[107];  7 char s1[107],s2[107];  8 int f[107][107];  9 int Max(int x,int y,int z) 10 {
     11     int tmp=-99999999; 12     if(tmp
          
           >n>>s1; 24         cin>>m>>s2; 25         for(i=0;i