NC220677. 商品摆放
描述
输入描述
第一行三个以空格分隔的整数。
第二行个以空格分隔的整数数组
，表示初始的时候第
个位置摆放着第
接下来的的矩阵，其中第
列代表
，表示这2种商品如果摆放在相邻位置会产生的额外收益。
输出描述
输出一行，一个整数表示你可以获得的最大额外收益。
示例1
输入:
4 1 3 1 4 2 0 3 0 1 3 0 0 0 0 0 0 0 1 0 0 0
输出:
3
说明:
如果不移除任何商品，则额外收益总和为pypy3(pypy3.6.1) 解法, 执行用时: 178ms, 内存消耗: 22256K, 提交时间: 2021-05-11 10:14:08
s = input()
n,k,m = list(map(int,s.split()))
s = input()
objs = list(map(int,s.split()))
weight = []
for i in range(n):
s = input()
tmp_list = list(map(int,s.split()))
weight.append(tmp_list)
weight.append([0] * n)
row = m+2
col = k+1
dp = []
for i in range(row):
tmp_list = [0]*col
dp.append(tmp_list)
for i in range(row):
for j in range(col):
for t in range(1,i):
if 0<=i-t<row and 0<=j-t+1<col and 0<=i-1<m and 0<= i-t-1 < m:
dp[i][j] = max(dp[i][j],dp[i-t][j-t+1] + weight[objs[i-1]-1][objs[i-t-1] -1])
res = -1
for i in range(row):
if dp[i][-1] > res:
res = dp[i][-1]
print(res)
C++(clang++11) 解法, 执行用时: 11ms, 内存消耗: 732K, 提交时间: 2021-05-08 16:06:47
#include<bits/stdc++.h>
using namespace std;
int a[205],mp[205][205],DP[205][205];
int main()
{
int i,j,len,n,t,m,ans=0;
scanf("%d%d%d",&n,&t,&m);
for(i=1;i<=m;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)scanf("%d",&mp[i][j]);
for(i=1;i<=m;i++)
{
for(j=0;j<=t;j++)
{
for(len=0;len<=min(i-1,j);len++)DP[i][j]=max(DP[i][j],DP[i-1-len][j-len]+mp[a[i]][a[i-1-len]]);
ans=max(ans,DP[i][j]);
}
}
printf("%d\n",ans);
return 0;
}