求助!P1854

回复帖子

@微分几何 2020-11-22 11:51 回复
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
long long dp[maxn][maxn];
vector<vector<vector<int> > > fang;
long long a[maxn][maxn],n,m;

bool cmp(int f1,int f2)
{
    for(int i=0;i<n;i++)
    {
        if(fang[n][f1][i]<fang[n][f2][i])   return false;
        else if(fang[n][f1][i]>fang[n][f2][i])  return true;
    }
    return false;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=0;i<=n;i++)
    {
        fang.push_back({});
        for(int j=0;j<=m;j++)
        {
            fang[i].push_back({});
            for(int k=0;k<=n;k++)
            {
                fang[i][j].push_back(0);
            }
        }
    }
    long long max=a[1][1],d=1;
    dp[1][1]=max;
    fang[1][1][0]=1;
    for(int i=2;i<=m;i++)
    {
        if(a[1][i]>max)
        {
            max=a[1][i];
            d=i;
        }
        dp[1][i]=max;
        fang[1][i][0]=d;
    }
    for(int f=2;f<=n;f++)
    {
        for(int v=1;v<=m;v++)//表示前f个花束,放在前v个花瓶里的最大美观 
        {
            if(v<f) continue;

            if(f<=v-1&&dp[f][v]<=dp[f][v-1])
            {
                if(dp[f][v]<dp[f][v-1])
                {
                    for(int i=0;i<f;i++)
                    {
                        fang[f][v][i]=fang[f][v-1][i];
                    }
                }
                if(dp[f][v]==dp[f][v-1])
                {
                    int p=0;
                    for(int i=0;i<f;i++)
                    {
                        if(fang[f][v][i]<fang[f][v-1][i])   break;
                        if(fang[f][v][i]>fang[f][v-1][i])
                        {
                            p=1;
                            break;
                        }
                    }
                    if(p==1)
                    {
                        for(int i=0;i<f;i++)
                        {
                            fang[f][v][i]=fang[f][v-1][i];
                        }
                    }
                }
                dp[f][v]=dp[f][v-1];
            }

            if(dp[f][v]<=dp[f-1][v-1]+a[f][v])
            {
                if(dp[f][v]<dp[f-1][v-1]+a[f][v])
                {
                    for(int i=0;i<f-1;i++)
                    {
                        fang[f][v][i]=fang[f-1][v-1][i];
                    }
                }
                if(dp[f][v]==dp[f][v-1]+a[f][v])
                {
                    int p=0;
                    for(int i=0;i<f-1;i++)
                    {
                        if(fang[f][v][i]<fang[f-1][v-1][i]) break;
                        if(fang[f][v][i]>fang[f-1][v-1][i])
                        {
                            p=1;
                            break;
                        }
                    }
                    if(p==1)
                    {
                        for(int i=0;i<f-1;i++)
                        {
                            fang[f][v][i]=fang[f-1][v-1][i];
                        }
                    }
                }
                fang[f][v][f-1]=v;
                dp[f][v]=dp[f-1][v-1]+a[f][v];
            }
        }
    }

    vector<int> ans;
    int jia=0;
    for(int i=n;i<=m;i++)
    {
        if(dp[n][i]>jia)
        {
            ans.clear();
            jia=dp[n][i];
            ans.push_back(i);
        }
        else if(dp[n][i]==jia)
        {
            ans.push_back(i);
        }
    }

    sort(ans.begin(),ans.end(),cmp);

    cout<<jia<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<fang[n][ans[0]][i]<<" ";
    }
    cout<<endl;
    return 0;
}

只有85分,求大佬指导

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。