Python3 解法, 执行用时: 277ms, 内存消耗: 4892K, 提交时间: 2022-06-21 09:33:24

n,k=map(int,input().split())
a=[0]
b=[0]
dp=[[0 for x in range(1001)] for y in range(11)] #n个靶子，x枝箭
suma=  0
for _ in range(n):
    x,y = map(int,input().split())
    a.append(x)
    b.append(y)
    suma=suma + x
for i in range(1,n+1):
    for j in range(1,suma+1):
        l = 0
        res = 0
        while l<= j and l<=a[i]:
            if l==a[i]:
                res = b[i]
            dp[i][j] =  max(dp[i][j],dp[i-1][j-l]+i*l*10+res)
            l = l +1

for i in range(1,suma+1):
    if dp[n][i] >=k:
        print(i)
        break
else:
    print('wa')
    
    



        
    

C++ 解法, 执行用时: 8ms, 内存消耗: 444K, 提交时间: 2022-04-04 22:15:55

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int q[100][1000];
int w[100];
long long f[1100];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>a>>b;
		int t=1;
		while(t<=a){
			q[i][t]=t*i*10+(t==a)*b;
			t++;
		}
		w[i]=t;
	}
	for(int i=1;i<=n;i++){
		for(int j=1050;j>=0;j--){
			for(int k=1;k<=w[i];k++){
				if(j>=k){
					f[j]=max(f[j],f[j-k]+q[i][k]);
				}
			}
		}
	}
	int d=lower_bound(f,f+1020,k)-f;
	if(d==1020)cout<<"wa";
	else cout<<d;
}