题解

157 条题解

  • 6
    @ 2017-05-08 09:08:50
    /*
    经典问题,f[x][i][j][k]表示第x步三个人分别在第i行,第j行,第k行时所能达到最大值,
    i,j,k顺推逆推皆可,因为用到的是f[x-1][][][];
    初值为f[1][1][1][1]=a[1][1];
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <iomanip>
    #include <cstdlib>
    using namespace std;
    
    int f[41][21][21][21];
    int n;
    int a[22][22];
    
    int max1(int a,int b,int c,int d,int f,int g,int h,int i)
    {
        int ans;
        ans=max(a,b);
        ans=max(ans,c);
        ans=max(ans,d);
        ans=max(ans,f);
        ans=max(ans,h);
        ans=max(ans,i);
        ans=max(ans,g);
        return ans;
    }
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        f[1][1][1][1]=a[1][1];
        for(int x=1;x<=2*n-1;x++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    for(int k=1;k<=n;k++)
                    {
                        int i1=x-i+1;int j1=x-j+1;int k1=x-k+1;
                        if(i1<0||j1<0||k1<0)    continue;
                        f[x][i][j][k]=max1(f[x-1][i-1][j][k],f[x-1][i][j-1][k],
                                          f[x-1][i][j][k-1],f[x-1][i-1][j-1][k],
                                          f[x-1][i-1][j][k-1],f[x-1][i][j-1][k-1],
                                          f[x-1][i-1][j-1][k-1],f[x-1][i][j][k])+a[i][i1]+a[j][j1]+a[k][k1];//最后一个状态别忘了x也要-1
                        if(i==j)
                            f[x][i][j][k]-=a[i][i1];
                        if(j==k)
                            f[x][i][j][k]-=a[j][j1];
                        if(i==k)
                            f[x][i][j][k]-=a[i][i1];
                        if(i==k&&k==j)
                            f[x][i][j][k]+=a[i][i1];
                    }
        cout<<f[2*n-1][n][n][n]<<endl;
        return 0;
    }
         
    
  • 3
    @ 2018-04-13 16:47:08

    /*
    算是比较普通的dp写法吧,把六维降到四维写。
    */
    #include <iostream>
    #include <cmath>
    using namespace std;
    int mp[21][21],N,dp[41][21][21][21];
    int main()
    {
    cin>>N;
    int y1,y2,y3;
    for(int y=1;y<=N;y++)
    for(int x=1;x<=N;x++)
    cin>>mp[x][y];
    for(int s=1;s<=N+N-1;s++)
    for(int x1=1;x1<=s&&x1<=N;x1++)
    for(int x2=1;x2<=s&&x2<=N;x2++)
    for(int x3=1;x3<=s&&x3<=N;x3++)
    {
    y1=s-x1+1;y2=s-x2+1;y3=s-x3+1;//转换
    if(y1>N||y2>N||y3>N)continue;
    dp[s][x1][x2][x3]=max(
    max(max(dp[s-1][x1][x2][x3],dp[s-1][x1-1][x2][x3]),
    max(dp[s-1][x1-1][x2][x3-1],dp[s-1][x1-1][x2-1][x3])),
    max(max(dp[s-1][x1][x2][x3-1],dp[s-1][x1-1][x2-1][x3-1]),
    max(dp[s-1][x1][x2-1][x3],dp[s-1][x1][x2-1][x3-1])))
    +mp[x1][y1];//8个状态判断
    if(x1!=x2||y1!=y2)dp[s][x1][x2][x3]+=mp[x2][y2];//判断2与1的重叠
    if((x1!=x3||y1!=y3)&&(x2!=x3||y2!=y3))dp[s][x1][x2][x3]+=mp[x3][y3];//判断3的重叠
    }
    cout<<dp[N+N-1][N][N][N]<<endl;
    return 0;
    }

  • 3
    @ 2018-02-06 19:52:09
    #include <stack>
    #include <queue>
    #include <string>
    #include <cmath>
    #include <vector>
    #include <cctype>
    #include <cstdlib>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int a[25][25]={0},f[45][45][45][45]={0};
    
    int main()
    {  //代码看着比较难受,大家凑合着看吧
        ios :: sync_with_stdio(false);
        int n,m,t;
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        m=2*n-2;
        f[0][1][1][1]=a[1][1];//赋边界值,不要忘了
        for(int s=1;s<=m;s++)//三条线路共同开始,循环步数
            for(int i=1;i<=n;i++)//第1条
                for(int j=1;j<=n;j++)//第2条
                    for(int k=1;k<=n;k++)//第3条
                    {
                        if(i==j&&j==k)//三条线路重合的情况,一一列举
                            t=a[i][s+2-i];//知道了行就能知道列,公式:步数+2-行数,大家可以试验一下
                        else if(i==j)
                            t=a[i][s+2-i]+a[k][s+2-k];
                        else if(i==k)
                            t=a[i][s+2-i]+a[j][s+2-j];
                        else if(j==k)//两个点重合的情况
                            t=a[j][s+2-j]+a[i][s+2-i];
                        else //不重合的情况
                            t=a[i][s+2-i]+a[j][s+2-j]+a[k][s+2-k];
                        f[s][i][j][k]=max(f[s-1][i][j][k],max(f[s-1][i][j-1][k-1],max(f[s-1][i-1][j][k-1],max(f[s-1][i-1][j-1][k],max(f[s-1][i-1][j][k],max(f[s-1][i][j-1][k],max(f[s-1][i][j][k-1],f[s-1][i-1][j-1][k-1])))))))+t;
                    }//到达三个点有八种方案,max(求当前最优解)
        cout<<f[m][n][n][n]<<endl;
        return 0;
    }
    
    
  • 2
    @ 2017-09-17 10:53:16

    6维数组水过

    #include<bits/stdc++.h>
    using namespace std;
    int tot=0;
    short int a[21][21];
    short int dp[22][22][22][22][22][22];
    int GETMAX(int b1,int b2,int c1,int c2,int d1,int d2,int e1,int e2)
    {
    int m,p;
    int l=max(b1,b2);
    int t=max(c1,c2);
    if (t>l) m=t;
    else m=l;
    l=max(d1,d2);
    t=max(e1,e2);
    if (t>l) p=t;
    else p=l;
    return max(p,m);
    }
    int main()
    {
    int n,k;
    cin>>n;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    for (int i1=1;i1<=n;i1++)
    for (int j1=1;j1<=n;j1++)
    for (int i2=1;i2<=n;i2++)
    for (int j2=1;j2<=n;j2++)
    for (int i3=1;i3<=n;i3++)
    for (int j3=1;j3<=n;j3++)
    {
    dp[1][1][1][1][1][1]=a[1][1];
    dp[i1][j1][i2][j2][i3][j3]=GETMAX(dp[i1-1][j1][i2-1][j2][i3-1][j3],dp[i1-1][j1][i2-1][j2][i3][j3-1],dp[i1-1][j1][i2][j2-1][i3-1][j3],dp[i1-1][j1][i2][j2-1][i3][j3-1],dp[i1][j1-1][i2][j2-1][i3-1][j3],dp[i1][j1-1][i2][j2-1][i3][j3-1],dp[i1][j1-1][i2-1][j2][i3-1][j3],dp[i1][j1-1][i2-1][j2][i3][j3-1]);
    if (i1==i2&&j1==j2&&i1==i3&&j1==j3) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1];
    else
    if (i1==i2&&j1==j2) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i3][j3];
    else
    if (i1==i3&&j1==j3) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i2][j2];
    else
    if (i2==i3&&j2==j3) dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i2][j2];
    else dp[i1][j1][i2][j2][i3][j3]+=a[i1][j1]+a[i2][j2]+a[i3][j3];
    }
    cout<<dp[n][n][n][n][n][n];
    return 0;
    }

  • 1
    @ 2020-06-27 13:20:23

    4维dp,考虑三条路径走相同步数(s)的状态可以避免在之后撞上其他路径在之前取过的数(因为两条路撞在一起的时候经过的步数必相同)
    三条路所在的位置为(i,s-i),(j,s-j),(k,s-k)
    (for循环,都可以for循环

    #include<iostream>
    using namespace std;
    int f[45][25][25][25];
    int main()
    {
        int n;
        cin>>n;
        int v[25][25];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin>>v[i][j];
        
        f[0][0][0][0] = v[0][0];
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        for (int s = 1; s <= 2*n-2; s++)
            for (int i = 0; i <= min(s, n-1); i++)
                for (int j = 0; j <= min(s,n-1); j++)
                    for (int k = 0; k <= min(s, n-1); k++)
                    {
                        for (int d1 = 0; d1 < 2; d1++)
                            for (int d2 = 0; d2 < 2; d2++)
                                for (int d3 = 0; d3 < 2; d3++)
                                {
                                    int _i, _j, _k;
                                    _i = i - dx[d1];
                                    _j = j - dx[d2];
                                    _k = k - dx[d3];
                                    if (_i >= 0 && _i <= s && _j >=0 && _j <=s && _k >=0 && _k <=s)
                                    {
                                        int tmp = v[i][s-i] + v[j][s-j] + v[k][s-k];
                                        if (i==j)
                                            tmp -= v[i][s-i];
                                        if (j==k)
                                            tmp -= v[j][s-j];
                                        if (i==k)
                                            tmp -= v[i][s-i];
                                        if (i==j && j==k)
                                            tmp += v[i][s-i];
                                        f[s][i][j][k] = max(f[s][i][j][k], f[s-1][_i][_j][_k] + tmp);
                                    }
                                }
                    }
        cout<<f[2*n-2][n-1][n-1][n-1];
        return 0;
    }
    
  • 1
    @ 2019-03-10 19:22:16

    四重DP

    #include <cstdio>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    using namespace std;
    int n,ans;
    int d[50][25][25][25],g[25][25];
    inline int max8(int a,int b,int c,int d,int e,int f,int g,int h){
        return max(max(max(a,b),max(c,d)),max(max(e,f),max(g,h)));
    }
    int main(){
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) cin>>g[i][j];
        for(int s=2;s<=n+n;s++){
            for(int i=1;i<s;i++){
                for(int j=1;j<s;j++){
                    for(int k=1;k<s;k++){
                        d[s][i][j][k]=max8(d[s-1][i][j][k],d[s-1][i-1][j][k],d[s-1][i][j-1][k],d[s-1][i][j][k-1],d[s-1][i-1][j-1][k],d[s-1][i][j-1][k-1],d[s-1][i-1][j][k-1],d[s-1][i-1][j-1][k-1]);
                        d[s][i][j][k]+=g[s-i][i]+g[s-j][j]+g[s-k][k];
                        if(i==j) d[s][i][j][k] -= g[s-i][i];
                        else if(i==k) d[s][i][j][k] -= g[s-i][i];
                        else if(j==k) d[s][i][j][k] -= g[s-j][j];
                        if(i==j&&j==k) d[s][i][j][k] -= g[s-i][i];
                    }
                }
            }
        }
        cout<<d[2*n][n][n][n];
        return 0;
    }
    
    
  • 1
    @ 2017-10-23 16:52:41

    拆点费用流
    每个点只被取一次且可以被多次经过,感觉拆点比较好操作一些。
    建边时候注意不能建到图的外面QAQ

    
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    
    #define INF 2147483644
    
    #define all ((n * n) + 10)
    
    using namespace std;
    
    const int Maxn = 5010;
    
    struct node {
        int to, next, val, cap; 
    } e[Maxn];
    
    int a[110][110], n, tot = 1, h[Maxn], S, T, dis[Maxn], vis[Maxn], pre[Maxn];
    
    void Add(int u, int v, int c, int p) {
        e[++tot] = (node){v, h[u],  c, p}; h[u] = tot;
        e[++tot] = (node){u, h[v], -c, 0}; h[v] = tot;
    }
    
    int num(int x, int y) {return (x - 1) * n + y;}
    
    bool Bfs() {
        queue <int> Q;
        for(int i = S; i <= T + all; ++i) {
            dis[i] = -INF; vis[i] = 0; pre[i] = 0;
        }
        dis[S] = 0; Q.push(S);
        while(!Q.empty()) {
            int u = Q.front(); Q.pop(); vis[u] = 0;
            for(int i = h[u]; i; i = e[i].next) {
                int v = e[i].to;
                if(dis[v] < dis[u] + e[i].val && e[i].cap) {
                    dis[v] = dis[u] + e[i].val;
                    pre[v] = i;
                    if(!vis[v]) {
                        vis[v] = 1;
                        Q.push(v);
                    }
                }
            }
        }
        return dis[T + all] != -INF;
    }
    
    int Mcmf() {
        int temp = 0;
        while(Bfs()) {
            int s = INF;
            for(int i = pre[T + all]; i; i = pre[e[i ^ 1].to]) s = min(s, e[i].cap);
            for(int i = pre[T + all]; i; i = pre[e[i ^ 1].to]) e[i].cap -= s, e[i ^ 1].cap += s;
            temp += s * dis[T + all];
        } return temp;
    }
    
    int main() {
    //  freopen("t.in", "r", stdin);
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) scanf("%d", &a[i][j]);
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                Add(num(i, j), num(i, j) + all, 0, 2);
                Add(num(i, j), num(i, j) + all, a[i][j], 1);
            }
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(i == n && j == n) continue;
                if(j < n) Add(num(i, j) + all, num(i, j + 1), 0, 3);
                if(i < n) Add(num(i, j) + all, num(i + 1, j), 0, 3);
            }
        }
        S = 0, T = num(n, n);
        Add(S, num(1, 1), 0, 3);
        printf("%d\n", Mcmf());
        return 0;
    }
    
  • 1
    @ 2017-09-30 21:53:29
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int e[41][21][21][21];
    int W[21][21];
    int n;
    
    inline int MAX(int a,int b,int c,int d,int e,int f,int g,int h)
    {
        return max(a,max(b,max(c,max(d,max(e,max(f,max(g,h))))))); 
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                scanf("%d",&W[i][j]);
        e[1][1][1][1]=W[1][1];
        for(int x=1;x<n+n;++x)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    for(int k=1;k<=n;++k)
                    {
                        int i1=x-i+1;
                        int j1=x-j+1;
                        int k1=x-k+1;
                        if(i1<=0||j1<=0||k1<=0) continue;
                        int &NOW=e[x][i][j][k];
                        NOW=MAX(e[x-1][i-1][j][k],e[x-1][i][j-1][k],e[x-1][i][j][k-1],e[x-1][i-1][j-1][k],e[x-1][i][j-1][k-1],e[x-1][i-1][j][k-1],e[x-1][i-1][j-1][k-1],e[x-1][i][j][k])+W[i][i1]+W[j][j1]+W[k][k1];
                        if(i==j) NOW-=W[i][i1];
                        if(i==k) NOW-=W[i][i1];
                        if(j==k) NOW-=W[j][j1];
                        if(i==j&&j==k) NOW+=W[i][i1];
                    }
        printf("%d",e[n+n-1][n][n][n]);
        
        return 0;
    } 
    
  • 1
    @ 2017-09-08 21:51:05

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int f[41][21][21][21];
    int map[21][21];
    int N;
    int main()
    {
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
    scanf("%d",&map[i][j]);
    }
    }
    f[1][1][1][1]=map[1][1];
    for(int step=2;step<=2*N-1;step++){//枚举步数,假定走到 (1,1) 用了一步
    for(int x1=max(1,step-N+1);x1<=min(N,step);x1++){//x1,x2,x3 是用 step步走到横坐标为 x1,x2,x3的方格,
    for(int x2=max(1,step-N+1);x2<=min(N,step);x2++){//用min(),max()都是保证方格不越界的方式
    for(int x3=max(1,step-N+1);x3<=min(N,step);x3++){
    int delta=map[x1][step-x1+1]+map[x2][step-x2+1]+map[x3][step-x3+1];
    if(x1==x2) delta-=map[x1][step-x1+1];
    if(x1==x3) delta-=map[x1][step-x1+1];
    if(x2==x3) delta-=map[x2][step-x2+1];
    if(x1==x2&&x1==x3) delta+=map[x1][step-x1+1];//多减去了一次

    f[step][x1][x2][x3]=max(f[step-1][x1][x2][x3],max(f[step-1][x1-1][x2][x3],
    max(f[step-1][x1][x2-1][x3],max(f[step-1][x1][x2][x3-1],
    max(f[step-1][x1-1][x2-1][x3],max(f[step-1][x1-1][x2][x3-1],
    max(f[step-1][x1][x2-1][x3-1],f[step-1][x1-1][x2-1][x3-1])))))))+delta;

    }
    }
    }
    }
    cout<<f[2*N-1][N][N][N];
    return 0;
    }

  • 1
    @ 2017-07-28 13:16:05

    DP

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n;
    int a[20+1][20+1];
    int f[40+1][20+1][20+1][20+1];
    
    int main()
    {
        while (~scanf("%d",&n))
        {
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    scanf("%d",&a[i][j]);
            memset(f,0,sizeof(f));
            f[1][1][1][1]=a[1][1];
            for (int t=1;t<=2*n-1;t++)
                for (int i=1;i<=n;i++)
                    for (int j=1;j<=n;j++)
                        for (int k=1;k<=n;k++)
                        {
                            int x[3+1]={0,i,j,k};
                            int y[3+1]={0,t-i+1,t-j+1,t-k+1};
                            if (y[1]>0&&y[2]>0&&y[3]>0)
                            {
                                int max_f=oo_min;
                                max_f=max(max_f,f[t-1][x[1]][x[2]][x[3]]);
                                max_f=max(max_f,f[t-1][x[1]-1][x[2]][x[3]]);
                                max_f=max(max_f,f[t-1][x[1]][x[2]-1][x[3]]);
                                max_f=max(max_f,f[t-1][x[1]][x[2]][x[3]-1]);
                                max_f=max(max_f,f[t-1][x[1]-1][x[2]-1][x[3]]);
                                max_f=max(max_f,f[t-1][x[1]-1][x[2]][x[3]-1]);
                                max_f=max(max_f,f[t-1][x[1]][x[2]-1][x[3]-1]);
                                max_f=max(max_f,f[t-1][x[1]-1][x[2]-1][x[3]-1]);
                                f[t][x[1]][x[2]][x[3]]=max(f[t][x[1]][x[2]][x[3]],max_f+a[x[1]][y[1]]+a[x[2]][y[2]]+a[x[3]][y[3]]);
                                if (x[1]==x[2])
                                    f[t][x[1]][x[2]][x[3]]-=a[x[1]][y[1]];
                                if (x[1]==x[3])
                                    f[t][x[1]][x[2]][x[3]]-=a[x[1]][y[1]];
                                if (x[2]==x[3])
                                    f[t][x[1]][x[2]][x[3]]-=a[x[2]][y[2]];
                                if (x[1]==x[2]&&x[2]==x[3])
                                    f[t][x[1]][x[2]][x[3]]+=a[x[1]][y[1]];
                            }
                        }
            printf("%d\n",f[2*n-1][n][n][n]);
        }
    }
    

    网络流 Min Cost Max Flow

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m;
    vector<int> f;
    vector<int> e;
    vector<int> u;
    vector<int> pre;
    vector<int> vis;
    vector<vector<int> > a;
    vector<vector<int> > c;
    vector<vector<int> > p;
    vector<vector<int> > ce;
    vector<vector<int> > cw;
    deque<int> q;
    
    void add_edge_1(int x,int y,int c_v,int p_v)
    {
        cw[x].push_back(y);
        c[x].push_back(c_v);
        p[x].push_back(p_v);
        ce[y].push_back(cw[x].size()-1);
        cw[y].push_back(x);
        c[y].push_back(0);
        p[y].push_back(-p_v);
        ce[x].push_back(cw[y].size()-1);
    }
    
    int bfs_1(int s,int t,int *flow,int *cost)
    {
        f.resize(0);
        f.resize(cw.size(),0);
        f[s]=oo_max;
        e.resize(0);
        e.resize(cw.size(),-1);
        u.resize(0);
        u.resize(cw.size(),oo_max);
        u[s]=0;
        pre.resize(0);
        pre.resize(cw.size(),-1);
        pre[s]=s;
        vis.resize(0);
        vis.resize(cw.size(),0);
        for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
        {
            int now=q.front();
            for (int i=0;i<cw[now].size();i++)
                if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
                {
                    f[cw[now][i]]=min(c[now][i],f[now]);
                    e[cw[now][i]]=i;
                    u[cw[now][i]]=u[now]+p[now][i];
                    pre[cw[now][i]]=now;
                    if (vis[cw[now][i]]==0)
                        vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                }
        }
        (*flow)=f[t];
        (*cost)=u[t];
        return (pre[t]!=-1);
    }
    
    void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
    {
        int temp_flow,temp_cost;
        while (bfs_1(s,t,&temp_flow,&temp_cost))
        {
            for (int i=t;i!=s;i=pre[i])
                c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
            (*flow)+=temp_flow;
            (*cost)+=temp_cost;
        }
    }
    
    int main()
    {
        //while (~scanf("%d%d",&n,&m))
        while ((~scanf("%d",&n))&&(m=3)>0)
        {
            a.resize(0);
            a.resize(n+1);
            for (int i=1;i<=n;i++)
            {
                a[i].resize(n+1,0);
                for (int j=1;j<=n;j++)
                    scanf("%d",&a[i][j]);
            }
            int tot=n*n;
            cw.resize(0);
            cw.resize(2*tot+2);
            ce.resize(0);
            ce.resize(cw.size());
            c.resize(0);
            c.resize(cw.size());
            p.resize(0);
            p.resize(cw.size());
            for (int i=0;i<cw.size();i++)
            {
                cw[i].resize(0);
                ce[i].resize(0);
                c[i].resize(0);
                p[i].resize(0);
            }
            add_edge_1(0,1,m,0);
            add_edge_1(2*tot,cw.size()-1,m,0);
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                {
                    add_edge_1((i-1)*n+j,(i-1)*n+j+tot,1,-a[i][j]);
                    add_edge_1((i-1)*n+j,(i-1)*n+j+tot,m,0);
                    if (i>1)
                        add_edge_1((i-2)*n+j+tot,(i-1)*n+j,m,0);
                    if (j>1)
                        add_edge_1((i-1)*n+j-1+tot,(i-1)*n+j,m,0);
                }
            int ans_flow=0,ans_cost=0;
            min_cost_max_flow_1(0,cw.size()-1,&ans_flow,&ans_cost);
            printf("%d\n",-ans_cost);
        }
    }
    
    • @ 2017-07-28 17:45:07

      很H2O的题,网络流效率更高一些

  • 1
    @ 2017-05-09 22:00:27

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    const int maxn = 41;
    const int maxm = 22;
    int dp[maxn][maxm][maxm][maxm];
    int juzhen[maxm][maxm];
    bool used[maxm][maxm];

    int add_(int a,int b){
    if(!used[a][b]){
    used[a][b] = true;
    return juzhen[a][b];
    }
    else return 0;
    }

    int main(){
    memset(used,false,sizeof(used));
    //memset(0,dp,sizeof(dp));
    int n;
    cin >> n;
    for(int p = 1;p <= n;p++){
    for(int q = 1;q <= n;q++) cin >> juzhen[p][q];
    }
    dp[2][1][1][1] = juzhen[1][1];
    for(int p = 3;p <= 2*n;p++){
    for(int i = 1;i < min(p,n + 1);i++){
    if(p - i > n)continue;
    for(int j = 1;j < min(p,n + 1);j++){
    if(p - j > n)continue;
    for(int k = 1;k < min(p,n + 1);k++){
    if(p - k > n)continue;
    //cout << " here" <<"\n";
    int max_ = 0;
    //rrr
    if(i > 1 && j > 1 && k > 1){
    max_ = max(max_,dp[p - 1][i - 1][j - 1][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    // ddd
    if(p - i > 1 && p - j > 1 && p - k > 1){
    max_ = max(max_,dp[p - 1][i][j][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    // rrd
    if(i > 1 && j > 1 && p - k > 1){
    max_ = max(max_,dp[p - 1][i - 1][j - 1][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    // rdr
    if(i > 1 && p - j > 1 && k > 1){
    max_ = max(max_,dp[p - 1][i - 1][j][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    //rdd
    if(i > 1 && p - j > 1 && p - k > 1){
    max_ = max(max_,dp[p - 1][i - 1][j][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    //ddr
    if(p - i > 1 && p - j > 1 && k > 1){
    max_ = max(max_,dp[p - 1][i][j][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    //drd
    if(p - i > 1 && j > 1 && p - k > 1){
    max_ = max(max_,dp[p - 1][i][j - 1][k] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    //drr
    if(p - i > 1 && j > 1 && k > 1){
    max_ = max(max_,dp[p - 1][i][j - 1][k - 1] + add_(p - i,i) + add_(p - j,j) + add_(p - k,k));
    memset(used,false,sizeof(used));
    }
    //cout << max_ <<"\n";
    dp[p][i][j][k] = max_;
    }
    }
    }
    }
    cout << dp[2*n][n][n][n] << "\n" << endl;
    return 0;
    }

  • 1
    @ 2015-10-26 16:50:25

    再发一个网络流的题解,把MAX_CAPACITY改成任意正整数k,即可实现k取方格数
    主要思路就是拆点构图。
    把每个点 x 拆成 x1, x2,x1与x2之间有:
    + 一条容量为1,价值为x权值的边
    + 一条容量为MAX_CAPACITY,价值为0的边

    假设y, z分别为 x 右侧、下方的点,把 x2 与 y1、x2 与 z1 各连一条边,容量为MAX_CAPACITY,价值为0
    最后加上源点与汇点,最大费用流即可。我使用了SPFA寻找最长价值的路径。

    解释一下变量含义:
    + edge类型中,next指向的是同一起点的下一条边在E中的位置
    + E是边集,size 是 E 的大小
    + headIndex[i] 指向的是起点为 i 的头一条边在E中的位置
    + used, dist, queue, prev 用于最长路算法,其中 prev[i] 记录最长路中通往点 i 的边在E中的位置

    #include <stdio.h>
    #include <stdlib.h>

    #define NIL -1
    #define MAX_CAPACITY 3
    #define INF 10000000
    #define MIN(a,b) ((a)<(b)?(a):(b))

    typedef struct{
    int next;
    int from, to, value, f;
    } edge;

    edge E[5000];
    int headIndex[1000];
    int size = 0;

    short used[1000];
    int queue[10000];
    int dist[1000];
    int prev[1000];

    void addEdge1(int from, int to, int value, int capacity);
    void addEdge(int from, int to, int value, int capacity);
    int maxPath(int source, int sink, int numV);
    int maxValueFlow(int source, int sink, int numV);

    int main(){
    int n, numV;
    int x, y, source, sink, value;

    scanf("%d", &n);

    /*initialize*/
    for(x=0; x<1000; x++)
    headIndex[x] = NIL;

    /*build the network*/
    numV = 0;
    for(x=0; x<n; x++){
    for(y=0; y<n; y++){
    scanf("%d", &value);
    addEdge(numV, numV+1, value, 1); //connect numV & numV+1
    addEdge(numV, numV+1, 0, MAX_CAPACITY);
    if(x < n-1)
    addEdge(numV+1, numV+2*n, 0, MAX_CAPACITY); //connnect numV+1 & its downer neighbour, if exists
    if(y < n-1)
    addEdge(numV+1, numV+2, 0, MAX_CAPACITY); //connnect numV+1 & its righter neighbour, if exists
    numV += 2;
    }
    }
    source = numV, sink = numV+1;
    addEdge(source, 0, 0, MAX_CAPACITY); //source
    addEdge(numV-1, sink, 0, MAX_CAPACITY); //sink

    /*solve*/
    printf("%d\n", maxValueFlow(source, sink, numV+2));
    return 0;
    }
    void addEdge1(int from, int to, int value, int capacity){
    E[size].from = from;
    E[size].to = to;
    E[size].value = value;
    E[size].f = capacity;
    E[size].next = headIndex[from];
    headIndex[from] = size;
    size++;
    }
    void addEdge(int from, int to, int value, int capacity){
    addEdge1(from, to, value, capacity);
    addEdge1(to, from, -value, 0);
    }
    int maxPath(int source, int sink, int numV){
    int i, head = 0, tail = 0;
    for(i=0; i<numV; i++){
    used[i] = 0;
    prev[i] = NIL;
    dist[i] = -INF;
    }
    dist[source] = 0;
    queue[tail++] = source;
    while(head < tail){
    source = queue[head];
    used[source] = 0;
    i = headIndex[source];
    while(i != NIL){
    if(E[i].f > 0 && dist[E[i].to] < dist[source] + E[i].value){
    dist[E[i].to] = dist[source] + E[i].value;
    prev[E[i].to] = i;
    if(!used[E[i].to]){
    queue[tail++] = E[i].to;
    used[E[i].to] = 1;
    }
    }
    i = E[i].next;
    }
    head++;
    }
    return dist[sink];
    }
    int maxValueFlow(int source, int sink, int numV){
    int path, v, augment, value, ret = 0;
    while((value = maxPath(source, sink, numV)) > 0){
    augment = INF;
    for(v=sink; v!=source; ){
    path = prev[v];
    augment = MIN(augment, E[path].f);
    v = E[path].from;
    }
    for(v=sink; v!=source; ){
    path = prev[v];
    E[path].f -= augment;
    E[path^1].f += augment;
    v = E[path].from;
    }
    ret += value*augment;
    }
    return ret;
    }

    • @ 2016-04-14 22:19:30

      思路不错,参考了:)

  • 0
    @ 2017-01-23 18:00:29
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int f[21][21][21][21][21][21];
    int map[21][21];
    inline int max(int a,int b)
    {
        return a>b? a:b;
    }
    inline int maxx(int a,int b,int c,int d,int e,int f,int g,int h){
        a=max(a,b);
        a=max(a,c);
        a=max(a,d);
        a=max(a,e);
        a=max(a,f);
        a=max(a,g);
        a=max(a,h);
        return a;
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&map[i][j]);
            }
        for(int z=1;z<=n;z++)
            for(int x=1;x<=n;x++)
                for(int c=1;c<=n;c++)
                    for(int v=1;v<=n;v++)
                        for(int b=1;b<=n;b++)
                            for(int m=1;m<=n;m++)
                            {
                                f[z][x][c][v][b][m]=maxx(f[z-1][x][c-1][v][b-1][m],f[z-1][x][c-1][v][b][m-1],f[z-1][x][c][v-1][b-1][m],f[z][x-1][c-1][v][b-1][m],f[z-1][x][c][v-1][b][m-1],f[z][x-1][c-1][v][b][m-1],f[z][x-1][c][v-1][b-1][m],f[z][x-1][c][v-1][b][m-1])+map[z][x]+map[c][v]+map[b][m];
                                if(z==c&&c==b&&x==v&&v==m)f[z][x][c][v][b][m]-=2*map[z][x];
                                else if(z==c&&x==v)f[z][x][c][v][b][m]-=map[z][x];
                                else if(z==b&&x==m)f[z][x][c][v][b][m]-=map[z][x];
                                else if(c==b&&v==m)f[z][x][c][v][b][m]-=map[c][v];
                            }
        printf("%d",f[n][n][n][n][n][n]);
        return 0;
    }
    

    谢谢大佬的inline,比之前走方格多了2维,以为会爆了。。。。(判断好长。。。)

    • @ 2017-01-23 18:01:17

      max函数抄袭了下楼下大佬代码qwq。。。

  • 0
    @ 2016-11-05 17:18:39

    ORZ 楼下 inline 真神奇

    #include<iostream>
    #include<cstring>
    using namespace std;
    inline int max(int a,int b){
    return a>b? a:b;
    }
    const int maxn = 21;
    inline int max(int a,int b,int c,int d,int e,int f,int g,int h){
    a=max(a,b);
    a=max(a,c);
    a=max(a,d);
    a=max(a,e);
    a=max(a,f);
    a=max(a,g);
    a=max(a,h);
    return a;
    }
    int dp[maxn][maxn][maxn][maxn][maxn][maxn];
    int map[maxn][maxn];
    int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>map[i][j];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    for(int l=1;l<=n;l++)
    for(int o=1;o<=n;o++)
    for(int u=1;u<=n;u++)
    {
    dp[i][j][k][l][o][u]=max(dp[i-1][j][k-1][l][o-1][u],dp[i-1][j][k-1][l][o][u-1],dp[i][j-1][k-1][l][o-1][u],dp[i][j-1][k-1][l][o][u-1],dp[i-1][j][k][l-1][o-1][u],dp[i-1][j][k][l-1][o][u-1],dp[i][j-1][k][l-1][o-1][u],dp[i][j-1][k][l-1][o][u-1])+map[i][j]+map[k][l]+map[o][u];
    if(i==k&&j==l&&!(k==o&&l==u&&i==o&&j==u&&i==k&&j==l)) dp[i][j][k][l][o][u]-=map[i][j];
    if(k==o&&l==u&&!(k==o&&l==u&&i==o&&j==u&&i==k&&j==l)) dp[i][j][k][l][o][u]-=map[o][u];
    if(i==o&&j==u&&!(k==o&&l==u&&i==o&&j==u&&i==k&&j==l)) dp[i][j][k][l][o][u]-=map[o][u];
    if(k==o&&l==u&&i==o&&j==u&&i==k&&j==l) dp[i][j][k][l][o][u]-=2*map[o][u];
    }
    cout<<dp[n][n][n][n][n][n];
    return 0;
    }

  • 0
    @ 2016-10-04 10:49:19

    丑陋的六维DP。
    能过简直奇迹。
    刚开始TLE,重载了max套了个inline就AC,时间平均800ms一个点。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    #include<stack>
    #include<map>
    #include<string>
    #include<cmath>
    #include<vector>
    #include<sstream>
    #define inf 0x3f3f3f3f
    #define Rep(i,n) for(register int i = 1;i<=n;i++)
    using namespace std;
    
    short f[21][21][21][21][21][21];
    inline short max(short a,short b){
        return a>b?a:b;
    }
    int main(){
        int n,a[21][21];
        scanf("%d",&n);
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)scanf("%d",&a[i][j]);
        memset(f,0,sizeof(f));
        int m1,m2,m3,m4;
        Rep(i,n)
            Rep(j,n)
                Rep(p,n)
                    Rep(q,n)
                        Rep(u,n)
                            Rep(v,n){
                                m1 = max(f[i-1][j][p-1][q][u-1][v],f[i-1][j][p-1][q][u][v-1]);
                                m2 = max(f[i-1][j][p][q-1][u-1][v],f[i-1][j][p][q-1][u][v-1]);
                                m3 = max(f[i][j-1][p][q-1][u-1][v],f[i][j-1][p][q-1][u][v-1]);
                                m4 = max(f[i][j-1][p-1][q][u-1][v],f[i][j-1][p-1][q][u][v-1]);
                                f[i][j][p][q][u][v] = max(max(m1,m2),max(m3,m4));
                                if(i!=p&&i!=u&&p!=u&&j!=q&&j!=v&&q!=v)f[i][j][p][q][u][v] += a[i][j]+a[p][q]+a[u][v];
                                else if(i==p&&i==u&&p==u&&j==q&&j==v&&q==v)f[i][j][p][q][u][v] += a[i][j];
                                else if(i==p&&j==q)f[i][j][p][q][u][v]+=a[i][j]+a[u][v];
                                else f[i][j][p][q][u][v]+=a[i][j]+a[p][q];
                            }
        printf("%d\n",f[n][n][n][n][n][n]);
        return 0;
    }
    
  • 0
    @ 2016-09-18 20:57:28

    f[step][x1][x2][x3]表示第step步时选择x1x2x3的最优解。
    循环的时候x从1到n,
    用x=max(1,s-n+1) 其中1是防止x越界 s-n+1是防止y越界,
    因为s=x+y-1所以y=s-x+1<=n所以s-n+1<=x
    用x<=min(n,s) 是防止x越界

    DP的时候 因为上一步可以是x也可以是x-1 为了防止错误需将f={0}

    #include <cstdio>
    #include <algorithm>
    using std::max;
    using std::min;

    int n,A[25][25],f[50][25][25][25]={0};

    int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    scanf("%d",&A[i][j]);
    f[1][1][1][1]=A[1][1];
    for(int s=2;s<=2*n-1;s++)
    for(int x1=max(1,s-n+1);x1<=min(n,s);x1++)
    for(int x2=max(1,s-n+1);x2<=min(n,s);x2++)
    for(int x3=max(1,s-n+1);x3<=min(n,s);x3++){
    //s=x+y-1
    int add=A[x1][s-x1+1]+A[x2][s-x2+1]+A[x3][s-x3+1];
    if(x1==x2) add-=A[x1][s-x1+1];
    if(x1==x3) add-=A[x1][s-x1+1];
    if(x2==x3) add-=A[x2][s-x2+1];
    if(x1==x2&&x2==x3) add+=A[x1][s-x1+1];//容斥原理
    f[s][x1][x2][x3]=max(f[s-1][x1][x2][x3],max(f[s-1][x1][x2][x3-1],max(f[s-1][x1][x2-1][x3],max(f[s-1][x1][x2-1][x3-1],max(f[s-1][x1-1][x2][x3],max(f[s-1][x1-1][x2][x3-1],max(f[s-1][x1-1][x2-1][x3],f[s-1][x1-1][x2-1][x3-1])))))));
    f[s][x1][x2][x3]+=add;
    }
    printf("%d",f[2*n-1][n][n][n]);

    return 0;
    }

  • 0
    @ 2016-09-03 11:18:31

    我爱压行

    #include<iostream>
    using namespace std;
    int f[45][25][25][25],map[22][22];
    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>map[i][j];
    int step=2*n-1;
    for(int k=1;k<=step;k++)
    for(int i=1;i<=min(k,n);i++)//min必须加,开始没加只过了五组。因为当k<n时,3个人
    for(int j=1;j<=min(k,n);j++)//的横坐标不可能走到n
    for(int l=1;l<=min(k,n);l++)
    {
    int x=map[i][k-i+1]+map[j][k-j+1]+map[l][k-l+1];
    if(i==j)x-=map[j][k-j+1];
    if(j==l)x-=map[l][k-l+1];
    if(i==l)x-=map[i][k-i+1];
    if(j==i&&j==l)
    x=map[i][k-i+1];
    for(int x1=0;x1>=-1;x1--)
    for(int x2=0;x2>=-1;x2--)
    for(int x3=0;x3>=-1;x3--)
    f[k][i][j][l]=max(f[k][i][j][l],f[k-1][i+x1][j+x2][l+x3]+x);
    }
    cout<<f[step][n][n][n];
    }

  • 0
    @ 2016-05-20 08:34:47

    max()嵌套有点丑,将就着看看吧
    pascal
    uses math;
    var dp:array[0..21,0..21,0..21,0..21] of integer; //x1,y1,x2,x3
    map:array[0..20,0..20] of integer;
    n,x1,y1,x2,y2,x3,y3:integer;
    begin
    read(n);
    for x1:=1 to n do
    for y1:=1 to n do
    read(map[x1,y1]);
    for x1:=1 to n do
    for y1:=1 to n do
    for x2:=1 to x1 do
    for x3:=1 to x1 do begin
    y2:=x1+y1-x2;
    y3:=x1+y1-x3;
    //writeln(x1,' ',y1,' ',x2,' ',y2,' ',x3,' f',y3);
    dp[x1,y1,x2,x3]:=max(
    max(max(dp[x1-1,y1,x2,x3],
    dp[x1-1,y1,x2,x3-1]),
    max(dp[x1-1,y1,x2-1,x3],
    dp[x1-1,y1,x2-1,x3-1])),
    max(max(dp[x1,y1-1,x2,x3],
    dp[x1,y1-1,x2,x3-1]),
    max(dp[x1,y1-1,x2-1,x3],
    dp[x1,y1-1,x2-1,x3-1])))+map[x1,y1];
    if (x1<>x2) and (y1<>y2) then inc(dp[x1,y1,x2,x3],map[x2,y2]);
    if (x1<>x3) and (y1<>y3) and (x2<>x3) and (y2<>y3) then
    inc(dp[x1,y1,x2,x3],map[x3,y3]);
    end;
    write(dp[n,n,n,n]);
    end.

  • 0
    @ 2015-11-05 14:05:15

    DP

    Block code

    #include<cstdio>
    #include<cstring>
    int f[45][25][25][25];
    int g[25][25];
    int n;
    int i,j;
    int h,a,b,c;
    int x;
    int max(int a,int b)
    {
    return a>b?a:b;
    }
    int main()
    {
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    scanf("%d",&g[i][j]);
    memset(f,0,sizeof(f));
    for(h=2;h<=2*n;h++)
    for(a=1;a<h;a++)
    for(b=1;b<h;b++)
    for(c=1;c<h;c++)
    {
    x=g[a][h-a];
    if((50*a+h-a)!=(50*b+h-b))
    x+=g[b][h-b];
    if((50*c+h-c)!=(50*a+h-a)&&(50*c+h-c)!=(50*b+h-b))
    x+=g[c][h-c];
    f[h][a][b][c]=f[h-1][a][b][c];
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a][b][c-1]);
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a][b-1][c]);
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b][c]);
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a][b-1][c-1]);
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b][c-1]);
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b-1][c]);
    f[h][a][b][c]=max(f[h][a][b][c],f[h-1][a-1][b-1][c-1]);
    f[h][a][b][c]+=x;
    // printf("f[%d][%d][%d][%d][%d][%d]=%d\n",a,h-a,b,h-b,c,h-c,f[h][a][b][c]);
    }
    printf("%d",f[2*n][n][n][n]);
    return 0;
    }

  • 0
    @ 2015-10-24 19:59:22

    果真6维过不了,只能拿50分。压缩成四维即可秒杀。
    实在受不了那些丑陋的嵌套 MAX,所以发个可变长参数的 MAX以供参考。

    short MAX(int total, ...){
    int ret = 0, tmp;
    va_list args;
    va_start(args, total);
    while(total--){
    tmp = va_arg(args, int);
    if(ret < tmp)
    ret = tmp;
    }
    va_end(args);
    return (short)ret;
    }

    使用时要包含 <stdarg.h> 这个头文件。调用时,第一个参数需填写总共有多少数要比较。如:MAX(5, a, b, c, d, e)

信息

ID
1143
难度
4
分类
动态规划 点击显示
标签
递交数
3434
已通过
1434
通过率
42%
被复制
6
上传者