试题编号： 201809-4 试题名称： 再卖菜 记忆化搜索

这题一看就是搜索，然后我不会写，咯咯咯。
看了题解发现好简单，这是一个递推式，令
d[n] 为第n家第一天的菜价 a[n]为第n家第二天的菜价
则 (d[n-1]+d[n]+d[n+1]) / 3 = a[n]
d[n+1] = 3 * a[n] - d[n-1] - d[n] + k (k=0,k=1,k=2)
递推一下就可以了，但是对于第n天，n-1天的菜价为x，第n天的菜价为y , f [ n ] [ x ] [ y ] 会被多次搜索，所以打一个标记，不搜索第二次。

#include <bits/stdc++.h>
using namespace std;

int a[305],b[305];
int t;
int f[305][305][305];

void dfs(int n,int x,int y)
{
    if (f[n][x][y]) return ;
    f[n][x][y]=1;

    if (n==t) {
        if ((y+x)/2==a[t]) {
            for (int i=1;i<=t;i++) {
                printf("%d",b[i]);
                if (i!=t) putchar(' ');
                else putchar('
');
            }
            exit(0);
        }

    }

    for (int i=0;i<3;i++) {
        b[n+1]=3*a[n]-x-y+i;
        if (b[n+1]>=1)
            dfs(n+1,y,b[n+1]);
    }
}


int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);

    for (int i=1;i<=t;i++) {
        scanf("%d",&a[i]);
    }

    for (int i=1;i<=2*a[1];i++) {
        b[1]=i;
        b[2]=2*a[1]-i;
        dfs(2,b[1],b[2]);

        b[1]=i;
        b[2]=2*a[1]-i+1;
        dfs(2,b[1],b[2]);
    }
    return 0;
}