///矩阵连乘

#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;
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<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;
#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;
}

///子集和

#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;
}

View Code