小朋友穿花衣

第一眼就感觉是递归

但是即使我用了剪枝，还是超时了

代码如下：

#include<stdio.h>
void dg(int id, int style, int v);
int maxn, n, m, value[100][10], maxv[100];

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            scanf("%d", &value[i][j]);
            maxv[i] = (maxv[i] > value[i][j]) ? maxv[i] : value[i][j];
        }
    //处理maxv
    for(int i = 0; i < n; i++)
    {
        maxv[i] = 0;
        for(int j = i + 1; j < n; j++)
            maxv[i] += maxv[j];
    }
    //递归
    for(int i = 0; i < m; i++)
        dg(0, i, value[0][i]);
    //输出
    printf("%d", maxn);

    return 0;
}
void dg(int id, int style, int v)
{
    if(v + maxv[id] < maxn) return;
    if(id == n - 1){maxn = v;  return;}
    for(int i = 0; i < m; i++)
    {
        if(i == style)  continue;
        dg(id + 1, i, v + value[id + 1][i]);
    }
    return;
}

然后换了一个思路，只比较最大和第二大的，但是有错误

代码如下：

#include<stdio.h>
struct Num{
    int id;
    int v;
}maxv[100], secv[100];
void dg(int id, int style, int v);
int maxn, n, m, value[100][10], left[100];

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            scanf("%d", &value[i][j]);
            if(maxv[i].v < value[i][j])
            {
                secv[i].v = maxv[i].v, secv[i].id = maxv[i].id;
                maxv[i].v = value[i][j], maxv[i].id = j;
            }
            else if(maxv[i].v == value[i][j])
                maxv[i].id = -1;
            else if(secv[i].v < value[i][j])
                secv[i].v = value[i][j], secv[i].id = j;
            else if(secv[i].v == value[i][j])
                secv[i].id = -1;
        }
    }
    //处理left
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            left[i] += maxv[j].v;
    //递归
    dg(0, maxv[0].id, maxv[0].v);
    dg(0, secv[0].id, secv[0].v);
    //输出
    printf("%d", maxn);

    return 0;
}
void dg(int id, int style, int v)
{
    if(v + left[id] < maxn)  return;
    if(id == n - 1){maxn = v;  return;}
    if(style == -1 || maxv[id + 1].id != style)  dg(id + 1, maxv[id + 1].id, v + maxv[id + 1].v);
    if(secv[id + 1].v && (style == -1 || secv[id + 1].id != style))  dg(id + 1, secv[id + 1].id, v + secv[id + 1].v);
    return;
}

然后又将第一个代码再改进了一下，还是超时（先递归较大的数）

代码如下：

#include<stdio.h>
struct Num{
    int id;
    int v;
}maxv[100], secv[100];
void dg(int id, int style, int v);
int maxn, n, m, value[100][10], left[100];

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            scanf("%d", &value[i][j]);
            if(maxv[i].v < value[i][j])
            {
                secv[i].v = maxv[i].v, secv[i].id = maxv[i].id;
                maxv[i].v = value[i][j], maxv[i].id = j;
            }
            else if(maxv[i].v == value[i][j])
                maxv[i].id = -1;
            else if(secv[i].v < value[i][j])
                secv[i].v = value[i][j], secv[i].id = j;
            else if(secv[i].v == value[i][j])
                secv[i].id = -1;
        }
    }
    //处理left
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            left[i] += maxv[j].v;
    //递归
    dg(0, maxv[0].id, maxv[0].v);
    dg(0, secv[0].id, secv[0].v);
    //输出
    printf("%d", maxn);

    return 0;
}
void dg(int id, int style, int v)
{
    if(v + left[id] < maxn)  return;
    if(id == n - 1){maxn = v;  return;}
    if(style == -1 || maxv[id + 1].id != style)  dg(id + 1, maxv[id + 1].id, v + maxv[id + 1].v);
    if(secv[id + 1].v && (style == -1 || secv[id + 1].id != style))  dg(id + 1, secv[id + 1].id, v + secv[id + 1].v);
    return;
}

最后我突然想到，这好像可以用动态规划做（受不了了）

感觉到了自己的先入为主

代码如下：

#include<stdio.h>
int n, m, dp[100][10];

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &dp[i][j]);
    //动态规划
    for(int i = 1; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            int tmp = 0;
            for(int k = 0; k < m; k++)
            {
                if(k == j)  continue;
                tmp = (tmp > dp[i - 1][k]) ? tmp : dp[i - 1][k];
            }
            dp[i][j] += tmp;
        }
    //输出
    int tmp = 0;
    for(int i = 0; i < m; i++)
        tmp = (tmp > dp[n - 1][i]) ? tmp : dp[n - 1][i];
    printf("%d", tmp);

    return 0;
}

瞬间过了，这就是动态规划

哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊