OI

【做题笔记】2018.1.6

天哪，都18年了……

寒假动规刷题计划，没有复习期末考，忍不住来做题了。

openjudge1768：最大子矩阵

虽然是放在DP题里的，但是看到n<=100的矩阵，就想到了二维前缀和暴力解这题，A得很开心（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
int sum[105][105]={0},a[105][105]={0};
int ss(int x1,int y1,int x2,int y2){
    return sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];
}
int main(){
    int i,j,k,l,n,max=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++){
        scanf("%d",&a[i][j]);
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
      }
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        for(k=1;k<=i;k++)
          for(l=1;l<=j;l++)
            if(ss(k,l,i,j)>max)max=ss(k,l,i,j);
    printf("%d",max);
    return 0;
}

1808：公共子序列

此题是最长公共子序列的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<string.h>
int max(int a,int b){
    if(a>b)return a;
    return b;
}
int main(){
    int i,j,f[205][205]={0},m;
    char a[205],b[205];
    while(scanf("%s",a)!=EOF){
      scanf("%s",b);
      m=0;
      f[1][1]=(a[0]==b[0]);
      for(i=1;i<=strlen(a);i++)
        for(j=1;j<=strlen(b);j++){
          f[i][j]=max(max(f[i][j-1],f[i-1][j]),f[i-1][j-1]+(a[i-1]==b[j-1]));
          m=max(m,f[i][j]);
        }
      printf("%d\n",m);
    }
    return 0;
}

1944：吃糖果

虽然是DP区的，但是一看到n<20就控制不住打暴力，一个dfs过了。然而看了题解发现竟然是斐波那契……（因此我得到了一个新的求斐波那契数列方法\bushi）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    #include<stdio.h>
    int sum=0;
    int dfs(int n){
        int j;
        for(j=1;j<=2;j++)
          if(n-j>=0){
              if(n-j==0)sum++;
              else dfs(n-j);
          }
    }
    int main(){
        int n;
        scanf("%d",&n);
        dfs(n);
        printf("%d",sum);
        return 0;
}