题解 P2066 【机器分配】

lyyi2003 · 2019-08-09 20:40:51 · 题解

这组数据可以hack掉大部分所谓标程：

3 6

10 10 1 1 1 1

10 1 10 1 1 1

10 10 10 1 1 1

正确做法应该在每个状态里记录这个状态的最大价值以及取到这个最大价值时的最小字典序，转移时如果最大价值相同，再比较字典序，取字典序小的转移。

正确的代码：

#include<bits/stdc++.h>
using namespace std;
#define N 107
int w[N][N];
struct str
{
    int x;
    string s;
    str operator +(int y)
    {
        return {x+y,s};
    }
    str operator +(char c)
    {
        return {x,s+c};
    }
    bool operator <(str a) const
    {
        return x<a.x||x==a.x&&s>a.s;
    }
}f[N][N];
int main()
{
    int n,m,i,j,k;
    //freopen("data.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&w[i][j]);
    for(i=1;i<=n;i++)
        for(j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j]+'0';
            for(k=1;k<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]+(char)('0'+k));
        }
    printf("%d\n",f[n][m].x);
    for(i=1;i<=n;i++)
        printf("%d %d\n",i,f[n][m].s[i-1]-48);
    return 0;
}