常州Eidht Day动规，考试

动态规划是对解最优问题的一种途径，不是特殊算法。和分治法一样，动态规划也是通过把一个
复杂的问题分解为相对简单的子问题的方式求
解，再组合出答案的方法。分治法是将问题划分
成一些独立的子问题，动态规划适用于子问题不
是独立的情况，也就是子问题包含公共的子子问
题。

for(int i = 1; i <= n; i++){ //跟踪样例体会一维DP的求解过程
    if[i] = 1; //可以把f[i]放在外面初始化为1，然后i从2到n求解
     for(int j = 1; j <= i-1; j++)
    if(a[j] <= a[i]) f[i] = max(f[i],f[j]+1);

角斗场

#include<bits/stdc++.h>
using namespace std;
char a[300][300];
int m,n,b[300][300]= {0},f=0,ans1=0,ans2=0,z1=0,z2=0;
int yx[5]= {0,-1,1,0,0},yy[5]= {0,0,0,-1,1};
void bfs(int x,int y) {
    int c[100000][2];
    b[x][y]=0;
    int aa=0,bb=1;
    c[1][1]=x;
    c[1][2]=y;
    do {
        aa++;
        for(int i=1; i<=4; i++) {
            int tx=c[aa][1]+yx[i],ty=c[aa][2]+yy[i];
            if(tx>=1 && tx<=n && ty>=1 && ty<=m && b[tx][ty]) {
                bb++;
                c[bb][1]=tx;
                c[bb][2]=ty;
                if(b[tx][ty]==2&&f) z1++;
                if(b[tx][ty]==3&&f) z2++;
                b[tx][ty]=0;
            }
        }
    } while(aa<bb);
    if(f){
        if(z2>=z1)
            z1=0;
        else
        z2=0;
    }
    ans1+=z1;ans2+=z2;
    z1=0; z2=0;
}
int main() {
    freopen("arena.in","r",stdin);
    freopen("arena.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++){
            cin>>a[i][j];
        if(a[i][j]==&#039;.&#039;)
            b[i][j]=1;
        if(a[i][j]==&#039;o&#039;)
            b[i][j]=2;
        if(a[i][j]==&#039;v&#039;)
            b[i][j]=3;
    }}
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            if(j==1||j==m||i==1||i==n)
            if(b[i][j]==1||b[i][j]==2||b[i][j]==3){
                bfs(i,j);
            }
            f=1;
            if(b[i][j]==2){z1=1,z2=0;
                bfs(i,j);}
            if(b[i][j]==3){z2=1,z1=0;
                bfs(i,j);}
            f=0;
        }
    cout<<ans1<<" "<<ans2;

    return 0;
}