///最大团

#include<bits/stdc++.h>
using namespace std;
int a[100][100];    
int x[100]; 
int n;  
int cn; 
int bestn;  

void backtrack(int i)
{
    if(i > n){
        bestn = cn;
        return;
    }
    
    int OK = 1;
    for(int j=1; j<i; j++){
        if(x[j] == 1 && a[i][j] == 0){  
            OK = 0;
            break;
        }
    }
    if(OK){ 
        x[i] = 1;
        cn++;
        backtrack(i+1);
        x[i] = 0;
        cn--;
    }
    if(cn+n-i > bestn){
        x[i] = 0;
        backtrack(i+1);
    }
}
int main()
{
    int t,m,u,v;
    scanf("%d",&t);
    for(int k=1; k<=t; k++)
    {
        cn = 0;
        bestn = 0;
        memset(a,0,sizeof(a));
        scanf("%d%d",&n,&m);
        for(int j=1; j<=m; j++){
            scanf("%d%d",&u,&v);
            a[u][v] = 1;
            a[v][u] = 1;
        }
        backtrack(1);
        printf("Case %d: %d\n",k,bestn);
    }
}
///子集和

#include<bits/stdc++.h>
using namespace std;
int n;
int c; 
int num[8000]; 
int x[8000];    
int bestIndex;
int flag=0; 
void backtract(int k,int s,int r){
    if(k>n){
        return;
    }
    x[k]=1;
    if(flag==0&&s+num[k]==c){
        for(int i=0;i<=k;i++){
            if(x[i]!=0){
                printf("%d ",num[i]);
            }
        }
        flag=1;
        printf("\n");
        return;
    }
    else if(s+num[k]+num[k+1]<=c&&flag==0){ 
        backtract(k+1,s+num[k],r-num[k]);
    }
    if(s+num[k+1]<=c&&s+r-num[k]>=c&&flag==0){
        x[k]=0;
        backtract(k+1,s,r-num[k]);
    }
    return;
}
int main()
{
    int r=0;  
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
        r+=num[i];
    }
    sort(num,num+n);
    backtract(0,0,r);
    if(flag==0){
        printf("No Solution!\n");
    }
    return 0;
}
///最大子矩阵和

#include<bits/stdc++.h>
using namespace std;
int ans(int g,int q[]){
   int cut=0;
   int ch=0;
    for(int i=1;i<=g;i++){
        if(ch>0)
        ch+=q[i];
        else
        ch=q[i];
        if(ch>cut)
        cut=ch;
    }
    return cut;
}
int main(){
     int n,m;
     int i,j,k;
     int a[401][401];
     while(~scanf("%d%d",&n,&m)){
     for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
     int sum=0;
     int b[401];
     for(i=1;i<=n;i++)
     {
        for(k=1;k<=m;k++)
           b[k]=0;
      for(j=i;j<=n;j++){
        for(k=1;k<=m;k++)
            b[k]+=a[j][k];
            int Max=ans(m,b);
            if(Max>sum)
                sum=Max;
        }
        }
        printf("%d\n",sum);
    }
     return 0;
}
///最长上升子序列

#include<bits/stdc++.h>
using namespace std;
int a[3002],b[3002],dp[3002];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int pos=1,maxx=1;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);
                if(dp[i]>=maxx)
                    pos=i;
                maxx=max(maxx,dp[i]);
            }
        }
    }
    printf("%d\n",maxx);
    b[1]=a[pos];
    int count=1;
    for(int i=pos-1;i>=1;i--){
        if(dp[i]==maxx-1){
            b[++count]=a[i];
            maxx=dp[i];
        }
    }
    for(int i=count;i>=1;i--){
        printf("%d ",b[i]);
    }
}
///矩阵连乘

#include<stdio.h>
int p[602],m[602][602];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d %d",&p[i-1],&p[i]);
        }
        for(int i=1; i<=n; i++)
            m[i][i]=0;
        for(int r=2; r<=n; r++){
            for(int i=1; i<=n-r+1; i++){
                int j=i+r-1;
                m[i][j]=m[i+1][j] + p[i-1]*p[i]*p[j];
                for(int k=i+1; k<j; k++){
                    int x=m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                    if(x<m[i][j]){
                        m[i][j]=x;
                    }
                }
            }
        }
        printf("%d\n", m[1][n]);
    }
}
///是否可达

#include<bits/stdc++.h>
using namespace std;
#define MAX 1003
int q[MAX][MAX],que[MAX];
int n,e,d;

void backtrack(int x,int y)
{
    if(x==y){   ///出口
        d=1;
    }
    que[x]=1;
    for(int i=1; i<=n; i++){
        if(q[x][i]==1 && que[i]==0){
            if(i==y){    ///判断是否到达
                d=1;
            }
            backtrack(i,y);
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&e))
    {
        int a,b,u,v,t;
        memset(q,0,sizeof(q));
        for(int i=1;i<=n;i++){
            q[i][i]=1;
        }
        for(int i=1;i<=e;i++){
            scanf("%d%d",&a,&b);
            q[a][b]=1;
        }
        scanf("%d",&t);
        while(t--)
        {
            d=0;
            memset(que,0,sizeof(que));
            scanf("%d%d",&u,&v);
            backtrack(u,v);
            if(d==1)
                printf("yes\n");
            else
                printf("no\n");
        }
        printf("\n");
    }
    return 0;
}
///n后问题

#include<bits/stdc++.h>
int n,sum,a[100];
bool place(int k)
{
    for(int i=1;i<k;i++){
        if((abs(k-i)==abs(a[i]-a[k])) || a[i]==a[k])
            return false;
    }
    return true;
}
void backtrack(int t)
{
    if(t>n)
        sum++;
    else{
        for(int i=1;i<=n;i++){
            a[t]=i;
            if(place(t))
                backtrack(t+1);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        sum=0;
        scanf("%d",&n);
        backtrack(1);
        printf("%d\n",sum);
    }
}
///捕牛记

#include<bits/stdc++.h>
using namespace std;
#define Max 100010
int main()
{
    int n,k,a,t,w;
    int x[Max],time[Max],q[Max];
    while(scanf("%d%d",&n,&k))
    {
        if(n==-1 && k==-1){ /// 停止循环
            break;
        }
        memset(x,0,sizeof(x));
        time[k]=-1;
        time[n]=0;
        x[n]=1;
        q[0]=n;t=0;w=1;
        while(t<w && time[k]==-1)
        {
            a=q[t];
            t++;
            if(a+1>=0 && a+1<Max && x[a+1]==0){ /// 从a -> a+1
                x[a+1]=1;
                time[a+1]=time[a]+1;
                q[w]=a+1;
                w++;
                if(w==Max){
                    w=0;
                }
            }
            if(a-1>=0 && a-1<Max && x[a-1]==0){ /// 从a -> a-1
                x[a-1]=1;
                time[a-1]=time[a]+1;
                q[w]=a-1;
                w++;
                if(w==Max){
                    w=0;
                }
            }
            if(a*2>=0 && a*2<Max && x[a*2]==0){ /// 从a -> a*2
                x[a*2]=1;
                time[a*2]=time[a]+1;
                q[w]=a*2;
                w++;
                if(w==Max){
                    w=0;
                }
            }
        }
        printf("%d\n",time[k]);
    }
    return 0;
}
///用DFS计算pre和post

#include<bits/stdc++.h>
int n,e,num=1;
int pre[1002],post[1002],pp[1002],c[1002][1002];
void dfs(int t)
{
    pp[t]=1;
    pre[t]=num++;
    for(int i=1;i<=n;i++){
        if(c[t][i]==1&&!pp[i])
            dfs(i);
    }
    post[t]=num++;
}
int main()
{
    int a,b;
    scanf("%d%d",&n,&e);
    for(int i=1;i<=e;i++){
        scanf("%d%d",&a,&b);
        c[a][b]=1;
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        printf("%d ",pre[i]);
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        printf("%d ",post[i]);
    }
}
///分组背包

#include<bits/stdc++.h>
using namespace std;
int v[1002][1002],p[1002][1002],k[1002],dp[1002];
int main()
{
    int t,n,c;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&c);
        for(int i=1;i<=n;i++){
            scanf("%d",&k[i]);
            for(int j=1;j<=k[i];j++){
                scanf("%d%d",&v[i][j],&p[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=c;j>=0;j--){
                for(int x=1;x<=k[i];x++){
                    if(v[i][x]<=j){
                        dp[j]=max(dp[j],dp[j-v[i][x]]+p[i][x]);
                    }
                }
            }
        }
        printf("%d\n",dp[c]);
    }
}
///多重背包

#include<bits/stdc++.h>
using namespace std;
int w[10002],v[10002],dp[10002];
int main()
{
    int t,n,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&c);
        int num=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            int x,y,m,res=1;
            scanf("%d%d%d",&x,&y,&m);
            while(res<m){
                w[++num]=x*res;
                v[num]=y*res;
                m-=res;
                res*=2;
            }
            if(m>0){
                w[++num]=x*m;
                v[num]=y*m;
            }
        }
        for(int i=1;i<=num;i++){
            for(int j=c;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        printf("%d\n",dp[c]);
    }
}
///二维背包
#include<bits/stdc++.h>
using namespace std;
int v[1002],w[1002],p[1002],dp[1002][1002];
int main()
{
    int t,n,c,l;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d%d%d",&n,&c,&l);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&v[i],&w[i],&p[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=c;j>=v[i];j--){
                for(int k=l;k>=w[i];k--){
                    dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+p[i]);
                }
            }
        }
        printf("%d\n",dp[c][l]);
    }
}
///超市搞活动

#include<bits/stdc++.h>
using namespace std;
int p[10002],q[10002],dp[10002];
int main()
{
    int c,n;
    while(~scanf("%d%d",&c,&n))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%d%d",&p[i],&q[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=q[i];j<=c;j++){
                dp[j]=max(dp[j],dp[j-q[i]]+p[i]);
            }
        }
        printf("%d\n",dp[c]);
    }
}
///租用游艇

#include<bits/stdc++.h>
using namespace std;
int r[202][202],dp[202];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            scanf("%d",&r[i][j]);
        }
    }
    dp[1]=0;
    dp[2]=r[1][2];
    for(int i=3;i<=n;i++){
        dp[i]=r[1][i];
        for(int j=2;j<i;j++){
            dp[i]=min(dp[i],dp[j]+r[j][i]);
        }
    }
    printf("%d\n",dp[n]);
}

View Code