19929:环形穿梭车调度

http://cs101.openjudge.cn/practice/19929/

随着双十一的到来，为了适应激增的快递量，特曼物流公司引进了一种自动化物流系统——穿梭车系统。某中转中心的环形穿梭车系统如图所示，它由一条环形轨道、一辆穿梭车、m个进货口、n个出货口组成。环形轨道两侧各有一条长直道，进出货口分别位于两条直道上，A侧为等距离排列的m个进货口，从左往右依次编号为1,2,…,m；B侧为等距离排列的n个出货口，从左往右依次编号为1,2,…,n。穿梭车内有一个货栈，它的容量是无限的，但只有一个进出货口。当一个货物进入时，车内原有货物必须全部向里移动一位，并将新的货物放在货栈最外侧；出货时，只有位于最外侧的货物可以被送出，送出后里面的货物必须全部向外移动一位。穿梭车沿逆时针运行，不能停止或倒退。某天晚上，中转中心马上就要停工了，但是还有很多包裹没有送出。现在A侧每个进货口均还有一个货物，每个货物都要通过穿梭车到达其目标出货口。1,2,…,m号进货口的货物目标出货口分别为A1,A2,…,Am（可以有重复），每个货物的重量分别为W1,W2,…,Wm（都是正整数）。现在穿梭车从1号进货口左侧开始运行，到达每个进货口时可以选择将货物送入车内，也可以继续前进；到达每个出货口时，可以将货物送出，也可以继续前进。由于时间紧张，穿梭车运行一圈回到出发点后，系统必须停止运行。现在请你调度这个穿梭车系统，合理安排穿梭车取货的位置，使穿梭车在这一圈能送出的货物总重量最大。

输入

第一行为两个正整数m,n，以空格分隔。其中m,n<=500 第二行为m个正整数，分别为A1,A2,…,Am，它们都不超过n，并且有可能相等。第三行为m个正整数，分别为W1,W2,…,Wm，它们都不超过500

输出

一个整数：穿梭车能送出的货物总重量最大值。

样例输入

5 3
1 2 3 2 1
5 4 3 4 2

样例输出

来源

by cs101-2019 19光华刘韫滕

python

n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j]=dp[i-1][j]
    dp[i][a[i]]=max(dp[i-1][:a[i]+1])+b[i]
print(max(dp[n]))

19929:环形穿梭车调度 ​

19929:环形穿梭车调度