B
假设先全选白天的,在选k个b-a大的,这样选最优
n,k=map(int,input().split())
a=[0]*n
b=[0]*n
c=[0]*n
res=0
for i in range(n):
a[i],b[i]=map(int,input().split())
c[i]=b[i]-a[i]
res+=a[i]
c.sort(reverse=True)
res+=sum(c[:k])
print(res)
F
比赛时没注意要保证经过车站数相同的情况下求最小时间
如果当前这个点站数可以由t这个站点更新过来且时间更短,则加入队列
还是要仔细看清题目
N=100005
M=200005
h=[-1]*N
e=[0]*2*M
ne=[0]*2*M
w=[0]*2*M
idx=0
from sys import stdin
def add(a,b,c):
global idx
e[idx]=a
w[idx]=c
ne[idx]=h[b]
h[b]=idx
idx+=1
n,m=map(int,stdin.readline().split())
for i in range(m):
a,b,c=map(int,stdin.readline().split())
add(a,b,c)
add(b,a,c)
d=[-1]*N
cnt=[0]*N
def solve():
from collections import deque
q=deque([1])
d[1]=0
cnt[1]=1
while q:
t=q.popleft()
i=h[t]
while i!=-1:
j=e[i]
if d[j]==-1:
d[j]=d[t]+w[i]
cnt[j]=cnt[t]+1
q.append(j)
elif cnt[j]==cnt[t]+1 and d[j]>d[t]+w[i]:
d[j]=d[t]+w[i]
q.append(j)
i=ne[i]
solve()
print(cnt[n],d[n])
E
刚开始写的超时了四层循环
n=int(input())
g=[0]*(n+1)
from sys import stdin
for i in range(1,n+1):
g[i]=list(map(int,stdin.readline().split()))
t=n//4
res=0
N=101
M=26
f=[[[[0]*M for i in range(M)] for i in range(M)] for i in range(M)]
for i in range(1,n+1):
for a in range(t,-1,-1):
for b in range(t,-1,-1):
for c in range(t,-1,-1):
for d in range(t,-1,-1):
if a-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+g[i][0])
if b-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+g[i][1])
if c-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+g[i][2])
if d-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+g[i][3])
print(f[t][t][t][t])
应该限制范围写简化成三层
n=int(input())
g=[0]*(n+1)
from sys import stdin
for i in range(1,n+1):
g[i]=list(map(int,stdin.readline().split()))
t=n//4
res=0
N=101
M=26
f=[[[[0]*M for i in range(M)] for i in range(M)] for i in range(M)]
for i in range(1,n+1):
for a in range(min(i,t),-1,-1):
for b in range(min(i-a,t),max((i-a-t-t)-1,-1),-1):
for c in range(min(i-a-b,t),max(i-a-b-t-1,-1),-1):
d=i-a-b-c
if d>t or d<0:continue
if a-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+g[i][0])
if b-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+g[i][1])
if c-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+g[i][2])
if d-1>=0:f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+g[i][3])
print(f[t][t][t][t])
这道题a,b,c,d正着循环也可以,因为i一定时,a+b+c+d=i,每种选择只能出现一次,保证了i这一层的数据肯定用的是i-1这一层的数据,不会用到i这一层的数据。