题目描述

坐标 (x1,x2,⋯,xn)，每一维坐标都必须是不超过 m 的正整数，那么一共就有 m^n个点。对于每个点，对于每个满足 0≤d≤n(m−1) 的 d，求出和这个点曼哈顿距离为 d的所有点的权值之和。

样例

输入：第一行两个正整数 n,m，然后是权值
3 2
1
2
4
8
16
32
64
128
输出：
1 22 104 128
2 41 148 64
4 73 146 32
8 134 97 16
16 97 134 8
32 146 73 4
64 148 41 2
128 104 22 1

动态规划

其实本来我用朴素的暴力方法写的，复杂度是m^2n，只过了两个点，意料之中。
然后看了资料 http://www.jeepxie.net/article/828725.html 发现用动态规划确实很妙。
dp[i][j][k]表示前i维，第j个点，距离为k的权值之和。核心思想是k+d的距离可以分成第i+1维的d距离和前i维的k距离。
O2优化之后运气好了可以AC，一般能过9个点。

C++ 代码

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000005
#define M 70005
using namespace std;
int Pow[N],dp[2][M][205],a[N],num[M][105],n,m,x[1010];


int main()
{

    scanf("%d%d",&n,&m);
    if(n==1){
      for(int i=1;i<=m;i++)scanf("%d",&x[i]);
      for(int i=1;i<=m;i++){
         for(int j=0;j<m;j++)
            {
                int ans=0;
                if(i>j)ans+=x[i-j];
                if(i+j<=m&&j)ans+=x[i+j];
                if(j!=m-1)printf("%d ",ans);else
                    printf("%d\n",ans);
            }
      }
    }else{
        int Q=1;
        for(int i=1;i<=n;i++)Q=Q*m;
        for(int i=0;i<Q;i++){
             int now=n,t=i;
             for(int j=1;j<=n;j++)num[i][j]=1;
              while(t)
            {
                num[i][now]+=t%m;
                t/=m;
                now--;
            }
            scanf("%d",&dp[0][i][0]);
        }
        Pow[n]=1;
        for(int i=n-1;i;i--)Pow[i]=Pow[i+1]*m;
         for(int i=1;i<=n;i++)
        {
            for(int j=0;j<Q;j++)
                for(int k=0;k<=n*(m-1);k++)
                    for(int d=0;d<m;d++)
                    {
                        if(k+d>n*(m-1))continue;
                        if(num[j][i]+d<=m)
                            dp[i%2][j][k+d]+=dp[(i-1)%2][j+d*Pow[i]][k];
                        if(num[j][i]-d>0&&d)
                            dp[i%2][j][k+d]+=dp[(i-1)%2][j-d*Pow[i]][k];
                    }
            for(int j=0;j<Q;j++)
                for(int k=0;k<=n*(m-1);k++)
                    dp[(i-1)%2][j][k]=0;
        }
       for(int i=0;i<Q;i++)
        for(int j=0;j<=n*(m-1);j++)
            if(j<n*(m-1))printf("%d ",dp[n%2][i][j]);else
                printf("%d\n",dp[n%2][i][j]);

    }
    return 0;
}