基础DP

从搜索改写为DP
UVA11450
dfs TLE,改写递归DP 190ms,递推 0ms

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1e2, INF = 0x3f3f3f3f;
int M,C,g[maxn][maxn];
int dfs(int cur,int money){
    if(money<0) return -INF;
    if(cur==C) return M-money;
    int ans = -INF;
    for(int i = 1; i <= g[cur][0]; i++){
        ans = max(ans,dfs(cur+1,money-g[cur][i]));
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int T; cin>>T;
    while(T--){
        cin>>M>>C;
        for(int i = 0; i < C; i++){
            cin>>g[i][0];
            for(int j = 1; j <= g[i][0]; j++){
                cin>>g[i][j];
            }
        }
        int ans = dfs(0,M);//NOTE 0-based
        if(ans!=-INF) cout<<ans<<endl;
        else cout<<"no solution"<<endl;
    }
    return 0;
} 
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1e2;
int M,C,g[maxn][maxn],dp[maxn][maxn];
int DP(int cur,int money){
    if(money<0) return -1;
    if(cur==C) return M-money;
/*******************************dp*******************************/
    if(dp[cur][money]!=-1) return dp[cur][money];
/*******************************dp*******************************/
    int ans = -1; //换成一个容易memset的数 
    for(int i = 1; i <= g[cur][0]; i++){
        ans = max(ans,DP(cur+1,money-g[cur][i]));
    }
    return dp[cur][money] = ans;
}
int main(){
    ios::sync_with_stdio(false);
    int T; cin>>T;
    while(T--){
/*******************************dp*******************************/
        memset(dp,-1,sizeof dp);
/*******************************dp*******************************/
        cin>>M>>C;
        for(int i = 0; i < C; i++){
            cin>>g[i][0];
            for(int j = 1; j <= g[i][0]; j++){
                cin>>g[i][j];
            }
        }
        int ans = DP(0,M);//NOTE 0-based
        if(ans!=-1) cout<<ans<<endl;
        else cout<<"no solution"<<endl;
    }
    return 0;
} 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e2;
bool dp[maxn][maxn];//余额能到达的状态 
int M,C,g[maxn][maxn];
int main(){
    ios::sync_with_stdio(false);
    int T; cin>>T;
    while(T--){
        memset(dp,0,sizeof dp);
        cin>>M>>C;
        for(int i = 0; i < C; i++){
            cin>>g[i][0];
            for(int j = 1; j <= g[i][0]; j++){
                cin>>g[i][j];
            }
        }
        for(int i = 1; i <= g[0][0]; i++) if(M-g[0][i]>=0) dp[0][M-g[0][i]]=1;
        
        for(int i = 1; i < C; i++){
            for(int j = M; j >= 0; j--){
                if(dp[i-1][j]){
                    for(int k = 1; k <= g[i][0]; k++){
                        if(j-g[i][k]>=0){
                            dp[i][j-g[i][k]] = 1;
                        }
                    }
                }
            }
        }
        for(int i = 0; i <= M; i++){
            if(dp[C-1][i]){
                printf("%d\n",M-i);//NOTE
                break;
            }
            if(i==M){
                printf("no solution\n");
                break;
            }
        }
    }
    return 0;
} 

O(n^2)的LIS
百练2757

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn =1010;
int dp[maxn],a[maxn],n,ans;
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        for(int i = 0; i < n; i++) dp[i] = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(a[i]>a[j]) dp[i] = max(dp[i],dp[j]+1);
            }
        }
        int ans = 0;
        for(int i = 0; i < n; i++) ans = max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
} 

O(nlogn)

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[1010],a[1010],n,ans;
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        memset(dp,INF,sizeof dp);
        for(int i = 0;i < n ;i++){
            *lower_bound(dp,dp+n,a[i]) = a[i]; 
        }
        printf("%d\n",lower_bound(dp,dp+n,INF)-dp);
    }
    return 0;
}

硬币问题
无限取O(nk)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[25],dp[25],k,n;
//int dfs(int cur,int k){}
int dfs(int k){
    if(k==0) return 0;
    if(k<0) return INF;
    if(dp[k]!=INF) return dp[k];
    int ans = INF;
    for(int i = 0; i < n; i++){//无限取 应该去除cur 
        ans = min(ans,1+dfs(k-a[i]));//不取或者取(取完后在递归时还可以继续取) 
    }
    return ans;
}
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        memset(dp,INF,sizeof dp);
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        int ans = dfs(k);
        if(ans==INF) printf("no solution.\n");
        else printf("%d\n",ans); 
    }
    return 0;
}

改写为递推式

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[25],dp[25],k,n;
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        memset(dp,INF,sizeof dp);dp[0] = 0;
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        for(int i = 0; i <= k; i++){
            for(int j = 0; j < n; j++){
                if(i-a[j]>=0) dp[i] = min(dp[i],1+dp[i-a[j]]);
            }
        }
        if(dp[k]==INF) printf("no solution.\n");
        else printf("%d\n",dp[k]); 
    }
    return 0;
}

取的次数
UVA674

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 10100;
int n,k; 
int a[maxn],dp[8][maxn];//数组过大memset也救不了你 
int dfs(int cur,int k){
    if(k==0) return 1;//满足+1 
    if(k<0) return 0;
    if(cur==n) return 0;//NOTE 满足k已经加1,不满足的自然是0 
    if(dp[cur][k]!=0) return dp[cur][k];//下面也是对的,这个不知道为啥更快 
//    if(dp[cur][k]!=-1) return dp[cur][k]; 
    return dp[cur][k] = dfs(cur+1,k)+dfs(cur,k-a[cur]); 
}
int main(){
//    int T; scanf("%d",&T);
    a[0]=50,a[1]=25,a[2]=10,a[3]=5,a[4]=1,n=5;
//    while(T--){
//        scanf("%d%d",&n,&k);
//        for(int i = 0; i < n; i++){
//            scanf("%d",&a[i]);
//        }
    memset(dp,0,sizeof dp);
    while(scanf("%d",&k)!=EOF){
//        memset(dp,0,sizeof dp); //NOTE
//        memset(dp,-1,sizeof dp);//只需1次 内部循环memset反复求子问题会TLE 
        int ans = dfs(0,k);
        if(!ans&&n) printf("no solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

很6的递推式

#include<cstdio>
int n,k,a[5]={1,5,10,25,50};
int dp[10010]={1};
int main(){
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 7489; j++)
            dp[j+a[i]]+=dp[j];
    while(scanf("%d",&k)!=EOF)
        printf("%d\n",dp[k]);
    return 0;
}

背包

整理自背包九讲

ZeroOnePack

背包体积V,N个物品,价值Wi,装入耗费Ci,求装入最大价值
设F[i,v]为前i个物品装入v时的最大值,F[i,v]=max(F[i-1,v],F[i-1,v-Ci]+Wi)

fill F[0,0...V]←0
for i←1 to n
    for v←Ci to V
        F[i][v] = max(F[i-1][v],F[i-1][v-C[i])+W[i])

注意到F[i,v]的递推一定是从左上方递推出结果的,使用一维从j求解j-C[i]是从上一维的i-1继承下来的,所以表示取1次

fill F[0...V]←0
for i←1 to n
    for v←V to Ci
        F[v] = max(F[v],F[v-C[i]]+W[i])

代码封装

void zeroOnePack(int F[],int C,int W){
    for(int v = V; v >= C; v--)
        F[v] = max(F[v],F[v-C]+W;
}

memset(F,0,sizeof F);
for(int i = 1; i <= n; i++)
    zeroOnePack(F,C[i],W[i]);

PS.如果要求背包恰好装满, F0设为0,F[1...V]设为-INF(表示体积为1...V时不可能恰好装满),否则全部设为0

CompletePack
无限取
设F[i,v]为前i个物品装入v时的最大值,F[i,v]=max(F[i-1,v],F[i,v-Ci]+Wi)
使用一维数组实现,j求解j-C[i]是从相同维度的i继承得来的,表示取一次
据说两个循环可以颠倒并带来常数优化,没有验证过

fill F[0...V]←0
for i←1 to n
    for v←Ci to V
        F[v] = max(F[v],F[v-C[i]]+W[i]);

代码封装

void completePack(int F[],int C,int W){
    for(int v = C; v <= V; v++)
        F[v] = max(F[v],F[v-C]+W;
}

memset(F,0,sizeof F);
for(int i = 1; i <= n; i++)
    completePack(F,C[i],W[i])

MultiPack
取有上限个

//O(V∑logMi)
void multiPack(int F[],int C,int W,int M){
    if(C*M >= V){
        completePack(F,C,W);
        return ;
    }
    int k = 1;
    while(k < M){
        zeroOnePack(F,k*C,k*W);
        M = M-k;
        k<<=1;
    }
    zeroOnePack(F,M*C,M*W);//余数
}
//O(VN)
//F[i][j]:用前i种物品填充j体积的背包后最多能剩几个第i种物品
memset(F[0],-1,sizeof F[0]); F[0][0] = 0;
for(int i = 1; i <= n; i++){
    for(int j = 0; j <= V; j++)
        if(F[i-1][j] >= 0)
            F[i][j] = M[i];
        else
            F[i][j] = -1;
    for(int j = 0; j <= V-C[i]; j++)
        if(F[i][j] >= 0)
            F[i][j+C[i]] = max(F[i][j+C[i],F[i][j]-1);
}

其它的问法:最多可放入多少个物品/多少容量/输出方案(顺序)/方案个数(sum)


HDU2844

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+7;
int F[maxn],C[maxn],W[maxn],M[maxn],V,n,ans; 
void zeroOnePack(int F[],int C,int W){
    for(int v = V; v >= C; v--)
        F[v] = max(F[v],F[v-C]+W);
}
void completePack(int F[],int C,int W){
    for(int v = C; v <= V; v++)
        F[v] = max(F[v],F[v-C]+W);
}
void multiPack(int F[],int C,int W,int M){
    if(M*C>=V){
        completePack(F,C,W);
        return ;
    }
    int k = 1;
    while(k<M){
        zeroOnePack(F,k*C,k*W);
        M=M-k;
        k<<=1;
    }
    zeroOnePack(F,M*C,M*W);
}
int main(){
    while(scanf("%d%d",&n,&V),n){
        ans=0;memset(F,0x80,sizeof F);F[0]=0;
        for(int i = 1; i <= n; i++)
            scanf("%d",&C[i]);
        for(int i = 1; i <= n; i++)
            scanf("%d",&M[i]);
        for(int i = 1; i <= n; i++)
            multiPack(F,C[i],C[i],M[i]);
        for(int i = 1; i <= V; i++)
            if(F[i]>0) ans++;
        printf("%d\n",ans);
    }
    return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int DP[123][222];

int main(){
//01背包 递推1
//从第i个中挑选总重量不超过j的最大价值物品 dp[n][j]=0 dp[i][j] = max (dp[i+1][j],dp[i+1][j-wi]+vi) / dp[i+1][j]
//从前i个中挑选。。。。。。。。。。。。。  dp[0][j]=0 dp[i][j] = max (dp[i-1][j],dp[i-1][j-wi]+vi) / ..........
    //dp[n]维memset 
    for(int i = n; i >= 1; i--){ // 
        for(int j = 0; j <= W; j++){
            if(j-w[i] >= 0)
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
            else
                dp[i][j] = dp[i+1][j];
        }
    }
    cout << dp[1][W]; 
    //dp[1]初始化 
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){
            if(j-w[i] >= 0)
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
            else
                dp[i+1][j] = dp[i][j];
        }
    }
    cout << dp[n+1][W];
//状态转移:从前i个中挑选总重量不超过j的最大价值物品转移到从前i+1中挑选...不超过j 和 不超过j+w[i]的状态 
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            if(j+w[i] <= W){
                dp[i+1][j+w[i]] = max(dp[i+1][j],dp[i+1][j+w[i]]+v[i]);
            }
        }
    }
    cout << dp[1][W];
//完全背包:前i个的取法:dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i]) /dp[i-1][j] 
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){
            if(j-w[i] >= 0)
                dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]); 
            else
                dp[i+1][j] = dp[i][j];
        }
    }
//一维DP的01背包: 
    for(int i = 1; i <= n; i++){
        for(int j = W; j >= w[i]; j--){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]); 
        }
    }
    cout << dp[W];
//一维DP的完全背包:
    for(int i = 1; i <= n; i++){ //下标[1...n] 
        for(int j = w[i]; j <= W; j++){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]); 
        }
    } 
    cout << dp[W]; 
//O(nlogn)的LIS问题:
//dp 0x3f3f3f3f初始化 
    for(int i = 1;i <= n ;i++){
        *lower_bound(dp+1,dp+n+1,a[i]) = a[i]; 
    } 
    cout << lower_bound(dp+1,dp+n+1,INF)-(dp+1) << endl; 
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
//int dp[]


int dfs(int cur,int W){
    if(cur==n+1) return 0;
    if(W<w[cur]) return dfs(cur+1,W);
    return max(dfs(cur+1,W),dfs(cur+1,W-w[cur])+v[cur]); 
} 

int DP(int cur,int W){
    if(cur==n+1) return dp[cur][W] = 0; //这里也要记忆 
    if(dp[cur][W]!=-1) return dp[cur][W];
    if(W<w[cur]) return dp[cur][W] = DP(cur+1,W);
    return dp[cur][W] = max(DP(cur+1,W),DP(cur+1,W-w[cur])+v[cur]);
}

int main(){
    //input init->0 
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){ //向背包容量的状态转移 
            if(j-w[i] < 0) dp[i][j] = dp[i+1][j];
            else dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]); 
        }
    }
    cout << dp[n][W] << endl; 
} 

int main(){
    //input init->0 
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){ //压缩 
            if(j-w[i] < 0) dp[i&1][j] = dp[(i+1)&1][j];
            else dp[i&1][j] = max(dp[(i+1)&1][j],dp[(i+1)&1][j-w[i]]+v[i]); 
        }
    }
    cout << dp[n&1][W] << endl; 
} 

int main(){
    //init dp[0]=0
    for(int i = 1; i <= n; i++){
        for(int j = W; j >= w[i]; j--){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]); //每次只需知道上面的和左上面的 
        }
    }
    cout << dp[W] << endl;
}

//ComPack

经典题目
https://people.cs.clemson.edu/~bcdean/dp_practice/

树形DP

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 1e3;
typedef vector<int> vi;

int level[maxn],parent[maxn];
vi G[maxn];
int sumC[maxn],sumS[maxn]; //孩子 孙子和 
int dp[maxn];
int maxLevel; 
//dp[i] =  //d[i]表示以i为根的子树的最大独立集 di = max(sum of d son of i , 1+ sum of grandson of i) 


void dfs(int u,int fa){ //更新level与parent 
    if(fa==-1)
        level[u] = 0;
    else
        level[u] = level[fa]+1;
    if(level[u] > maxLevel)
        maxLevel = level[u];
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fa) dfs(v,parent[v]=u);
    }
}


int rootDP(int u){
    parent[u] = -1;
    maxLevel = -1;
    dfs(u,p[u]); //建树 
    for(int i = maxLevel, i >= 0; i--){
        for(int j = 0; j < V; j++){
            if(level[j]==i){ // 一开始j是叶子节点 
                dp[j] = max(sumS[j]+1,sumC[j]);
                if(i-1>=0) //刷表法 
                    sumC[p[j]]+=dp[j];
                if(i-2>=0)
                    sumS[p[p[j]]]+=dp[j];
            }
        }
    }
    return dp[u]; 
} 

int main(){
    int T,u,v; scanf("%d",&T);
    while(T--){
        int V; scanf("%d",&V);
        for(int i = 0; i < V-1; i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int best = -1;
        for(int i = 0; i < V; i++){
            memset(sumC,0,sizeof sumC);
            memset(sumS,0,sizeof sumS);
            int temp = rootDP(i);
            if(temp > best) best = temp;
        }
        printf("%d\n",best);
    }
    return 0;
}

三维求和
UVA10755

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 30;
ll sum[maxn][maxn][maxn];
ll sum1(int x,int y,int z){//第k层1...x至1...y的总和 
    return sum[x][y][z]-sum[x][y][z-1];
}
ll Sum(int i1,int i2,int j1,int j2,int k){//第k层i1...i2至j1...j2的总和 
    return sum1(i2,j2,k)-sum1(i2,j1-1,k)-sum1(i1-1,j2,k)+sum1(i1-1,j1-1,k);
}
int x,y,z;
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&x,&y,&z);
        memset(sum,0,sizeof sum);
        for(int i = 1; i <= x; i++){
            for(int j = 1; j <= y; j++){
                for(int k = 1; k <= z; k++){
                    scanf("%lld",&sum[i][j][k]);
                    sum[i][j][k] += sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]
                                    -sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]
                                    +sum[i-1][j-1][k-1]; 
                }
            }
        }
        ll ans = 1ll<<63; ans=-ans;
        for(int i1 = 1; i1 <= x; i1++) for(int j1 = 1; j1 <= y; j1++)
            for(int i2 = i1; i2 <= x; i2++) for(int j2 = j1; j2 <= y; j2++){
                ll t = 0;
                for(int k = 1; k <= z; k++){
                    t+=Sum(i1,i2,j1,j2,k);
                    ans = max(ans,t);
                    if(t<0) t=0;
                }
            }
        if(T) printf("%lld\n\n",ans);
        else printf("%lld\n",ans);
    }
    return 0;
} 

记忆化
HDU1506

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll a[maxn],l[maxn],r[maxn];
ll n,tl,tr,ans;
int main(){
    while(scanf("%lld",&n),n){
        for(int i = 1; i <= n; i++){
            scanf("%lld",&a[i]);
            l[i]=i;r[i]=i;
        }
        for(int i = 2; i <= n; i++){//找出连续比自身高度大的区间 
            tl = l[i];
            while(tl>1&&a[i]<=a[tl-1]) tl = l[tl-1]; //NOTE:tl>1防止越界 && 记忆化防止TLE 
            l[i] = tl; 
            //如果左边界比自身高,那左边界的左边界(已知)肯定比自己高  
            //但while不可换成if
            //a1 = 4 a2 = 5 a3 = 2 l[2]=2 l[3]=1 只用记忆化则l[3]=2,用while则终止条件则t=1或al小于自身 
        }
        for(int i = n-1; i >= 1; i--){
            tr = r[i];
            while(tr<n&&a[i]<=a[tr+1]) tr = r[tr+1];
            r[i] = tr;
        }
        ans = 0;
        for(int i = 1; i <= n; i++){
            ans = max(ans,a[i]*(r[i]-l[i]+1));
        }
        printf("%lld\n",ans);
    }
    return 0;
} 

求__单调__的最大子矩阵,和上面思路一样,以每一行为底进行计算
HDU1505

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const long long INF = 1ll<<55;
const int maxn = 1010;
long long a[maxn],l[maxn],r[maxn];
long long T,n,m,tl,tr,ans;
char ch[5];
using namespace std;
int main(){
    int T; scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&m);
        memset(a,0,sizeof a);memset(l,0,sizeof l); memset(r,0,sizeof r);
        ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                scanf("%s",ch);
                if(ch[0] == 'R') a[j] = 0;
                else if(a[j]!=0) a[j]=a[j]+1;
                else a[j] = 1;
            }
            l[1] = 1; r[m] = m;
            for(int j = 2; j <= m; j++){
                tl = j;
                while(tl>1&&a[j]!=0&&a[j]<=a[tl-1]) tl = l[tl-1];
                l[j] = tl;
            }
            for(int j = m-1; j >= 1; j--){
                tr = j;
                while(tr<n&&a[j]!=0&&a[j]<=a[tr+1]) tr = r[tr+1];
                r[j] = tr;
            }
            for(int j = 1; j <= m; j++){
                ans = max(ans,a[j]*(r[j]-l[j]+1)*3);
            }
        }    
        printf("%lld\n",ans);
    } 
    return 0;
}

HDU2870
同理,但直接搬上面那个边界判断会WA,原因不太清楚

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1100;
int a[maxn],b[maxn],c[maxn],l[maxn],r[maxn];
int T,n,m,tl,tr,ans;
char str[maxn];
using namespace std;
void query(int qwert[]){
    for(int j = 1; j <= m; j++){
        l[j] = j;
        while(l[j]-1>=1&&qwert[j]<=qwert[l[j]-1]) l[j]=l[l[j]-1];
    }
    for(int j = m; j >= 0; j--){
        r[j] = j;
        while(r[j]+1<=m&&qwert[j]<=qwert[r[j]+1]) r[j]=r[r[j]+1];
    }
    for(int j = 1; j <= m; j++){
        ans = max(ans,qwert[j]*(r[j]-l[j]+1));
    }
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        ans = 0;
        memset(a,0,sizeof a);memset(b,0,sizeof b);memset(c,0,sizeof c);
        for(int i = 1; i <= n; i++){
            scanf("%s",str+1);
            for(int j = 1; j <= m; j++){
                if( (str[j]=='a'||str[j]=='w'||str[j]=='y'||str[j]=='z')) a[j]++;
                else a[j] = 0;
                if( (str[j]=='b'||str[j]=='w'||str[j]=='x'||str[j]=='z')) b[j]++;
                else b[j] = 0;
                if( (str[j]=='c'||str[j]=='x'||str[j]=='y'||str[j]=='z')) c[j]++;
                else c[j] = 0;
            }
            query(a);query(b);query(c);
        }    
        printf("%d\n",ans);
    } 
    return 0;
}

HDU2830

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1100;
int a[maxn],ta[maxn],l[maxn],r[maxn];
int T,n,m,tl,tr,ans,t;
char str[maxn];
using namespace std;
void query(int a[]){
    l[1] = 1; r[m] = m;
    for(int j = 2; j <= m; j++){
        tl = j;
        while(tl>1&&a[j]!=0&&a[j]<=a[tl-1]) tl = l[tl-1];
        l[j] = tl;
    }
    for(int j = m-1; j >= 1; j--){
        tr = j;
        while(tr<n&&a[j]!=0&&a[j]<=a[tr+1]) tr = r[tr+1];
        r[j] = tr;
    }
    for(int j = 1; j <= m; j++){
        ans = max(ans,a[j]*(r[j]-l[j]+1));
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        ans = 0;
        memset(a,0,sizeof a);
        memset(ta,0,sizeof ta);
        for(int i = 1; i <= n; i++){
            cin>>str+1;
            for(int j = 1; j <= m; j++){
                if(str[j]=='0') ta[j] = 0;
                else ta[j]++;
            }
            memcpy(a,ta,sizeof ta);
            sort(a,a+m);
            query(a);
        }
        cout<<ans<<endl;
    } 
    return 0;
}

http://www.cnblogs.com/TnT2333333/p/7114980.html

https://vjudge.net/article/128

https://wenku.baidu.com/view/3a48c1f8964bcf84b9d57be0

标签: 算法, 学习

添加新评论