模板1

最优子矩阵

 1 /*对于一个矩阵而言，如果我们将连续k行的元素纵向相加，并对相加后所得的数列求连续最大和，则此连
 2 
 3 续最大和就是一个行数为k的最优子矩阵！
 4 */
 5 
 6 #include<iostream>
 7 using namespace std;
 8 int rec[101][101];
 9 //int m=0;
10 //void get(int ans[101],int nums)
11 //{
12 //    int b = 0;
13 //    for(int i=0;i<nums;i++)
14 //    {
15 //        if(b<0)
16 //            b = ans[i];
17 //        else
18 //            b +=ans[i];
19 //        if(b>m)
20 //            m = b;
21 //    }
22 //}
23 int main()
24 {
25     int nums;
26     int result[101];
27     cin>>nums;
28     int m=0;
29     for(int i=0;i<nums;i++)
30     {
31         for(int j=0;j<nums;j++)
32         {
33             cin>>rec[i][j];
34         }
35     }
36     for(int i=0;i<nums;i++)
37     {
38         memset(result,0,sizeof(result));
39         for(int j=i;j<nums;j++)
40         {            
41             int b = 0;
42             for(int k=0;k<=nums;k++)
43             {
44                 result[k]+=rec[j][k];
45                 if(b<=0)
46                     b = result[k];
47                 else
48                     b +=result[k];
49                 if(b>m)
50                     m=b;
51             }
52 
53         }
54     }
55     cout<<m<<endl;
56     return 0;
57 }

View Code

括号匹配

 1 /*
 2 括号匹配问题
 3 前i个中 ) 的个数为 j个。
 4 初始化，dp[1][0]=1;
 5 
 6 设立 j 为 ) 比 ( 更加简单
 7 
 8 */
 9 
10 #include<stdio.h>
11 int dp[20][20];
12 
13 int main()
14 {
15     int i,j,n;
16     while(scanf("%d",&n)>0)
17     {
18         if(n%2==1)
19         {
20             printf("0
");
21             continue;
22         }
23         dp[1][0]=1;
24         for(i=2;i<=n;i++)
25         {
26             for(j=0;j<=i/2;j++)
27             {
28                 dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
29             }
30         }
31         printf("%d
",dp[n][n/2]);
32     }
33     return 0;
34 }

View Code

RMQ

 1 /*
 2 
 3 RMQ 求解区间最值问题。
 4 
 5   满足动态规范方程：
 6   dp[i][j]=min{ dp[i][j-1],dp[i+( 1<<(j-1) )][j-1]  }
 7   利用的是二分的思想，表示dp[i][j]，位置i开始，长度为j的最值
 8   分解成，dp[i][j-1] ，dp[i+( 1<<(j-1) )][j-1]
 9 
10 */
11 
12 #include<iostream>
13 #include<cstdlib>
14 #include<cstring>
15 #define N 1000
16 using namespace std;
17 
18 int dp[N][N];
19 int A[N];
20 
21 int hmin(int x,int y)
22 {
23     return x>y? x:y;
24 }
25 
26 int RMQ(int L,int R) //查询的操作
27 {
28     int k=0;
29     while(  (1<<(k+1))<=R-L+1 )k++;
30     return hmin(dp[L][k-1],dp[L+(1<<(k-1))][k-1]);
31 }
32 
33 void make_ini(int n)
34 {
35     int i,j,L,R,M;
36     for(i=1;i<=n;i++)  //初始化
37         dp[0][i]=A[i];
38 
39     for(j=1;(1<<j)<=n;j++) //元素编号从 1 到 n
40         for(i=1;i+j-1<=n;i++)
41             dp[i][j]=hmin(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
42 
43 /*
44     P198    
45         
46 */
47     scanf("%d",&M);
48     while(M--)
49     {
50         scanf("%d%d",&L,&R);
51         printf("%d
",RMQ(L,R));
52     }
53 }
54 
55 int main()
56 {
57     int n,i;
58     while(scanf("%d",&n)>0)
59     {
60         for(i=1;i<=n;i++)
61             scanf("%d",&A[i]);
62         make_ini(n);
63     }
64     return 0;
65 }

View Code

求二进制数中1的个数

 1 #include<stdio.h>
 2 int get(int i)
 3 {
 4     int count=0;
 5     while(i)
 6     {
 7         ++count;
 8         i=(i-1)&i;
 9     }
10     return count;
11 }
12 int main()
13 {
14     int i;
15     while(scanf("%d",&i)>0)
16     {
17         printf("%d
",get(i));
18     }
19 }

View Code

线段切割

 1 /*
 2 看了中学生的论文，
 3 学 线段切割
 4 
 5 
 6 线段
 7 a. ___________________.b
 8   
 9     c.___________.d
10      
11 */
12 
13 struct Line
14 {
15     int a;    //线段起始点
16     int b;    //线段终点
17     int longint; //长度
18 };
19 
20 bool Function(int a,int b,int c,int d) 
21 {
22     if(a>=d || c>=b) return false;
23     else return true;
24 }
25 //判断线段是否重叠。当满足a>=d || c>=b的时候，不满足.
26 
27 
28 
29 void Cut(int Num,int c,int d)
30 {
31     if(Line[Num].a<c) Add(Line[Num].a,c);
32     if(d<Line[Num].b) Add(d,Line[Num].b);
33     Delete(Num);
34 }
35 //切割线段过程。如最上方所示。
36 
37 /*
38 线段
39 a. ___________________.b
40   
41     c.___________.d
42 */
43 
44 
45 void Add(int a,int b)
46 {
47     total++;
48     Line[total].a=a;
49     Line[total].b=b;
50 }
51 //将一条线段增加到线段集合中
52 
53 
54 void Delete(int Num)
55 {
56     Line[Num]=Line[total];
57     total--;
58 }
59 //线段的删除过程，可以将集合中最后一天线段
60 //移到要删除线段的位置

View Code

石子合并

 1 /*
 2 f(n3)超时，超空间。
 3 */
 4 
 5 #include<stdio.h>
 6 #include<stdlib.h>
 7 int dp[10005][10005];
 8 int sum[10005]={0};
 9 int a[10005];
10 int mmin(int x,int y)
11 {
12     if(x<y)
13         return x;
14     else return y;
15 }
16 int main()
17 {
18     int n,i,j,k,len;
19     while(scanf("%d",&n)>0)
20     {
21         if(n==0)break;
22         for(i=1;i<=n;i++)
23         {
24             scanf("%d",&a[i]);
25             sum[i]=sum[i-1]+a[i];
26         }
27         for(len=2;len<=n;len++)//长度
28         {
29             for(i=1;i<=n-len+1;i++) //起点
30             {
31                 j=i+len-1; //终点
32                 dp[i][j]=0x7fff;
33                 for(k=1;k<j;k++)
34                     dp[i][j]=mmin(dp[i][j],dp[i][k]+dp[k+1][j]-sum[i-1]+sum[j]);
35             }
36         }
37         printf("%d
",dp[1][n]);
38     }
39     return 0;
40 }

View Code