8. 大哈爱闯关
题目ID：6020必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Time Limit Exceeded
30 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述
大哈最近报名了一个真人闯关节目，总共有 nn 关，如果他能通过 nn 关并且耗时最少那么他就能获得价值连城的作业大礼包。
节目里的每一关都会消耗大哈aiai的体力和bibi的时间，理论上来说他要获奖非常地难，但是作为节目的特邀嘉宾，节目组给他了一些特权。
- 他有 mm 次"跳过"的权利，当他发起"跳过"时，他可以直接通过当前关卡，不需要消耗他的体力和时间。
- 当他成功闯入第 KK 关时，他将多获得一次"跳过"的权利。（当然，他可以选择，在第 KK 关就使用）
大哈一开始的体力为 tt ，问大哈通关需要的最短时间。如果最终大哈还是无法通关，输出
-1输入格式
第一行，一个整数 nn
第二行，三个整数 t,m,Kt,m,K
第三行，n个整数 aiai
第四行，n个整数 bibi
输出格式
一个整数，表示大哈通关需要的最短时间，如果无法通过输出-1.
样例输入1
10 40 2 1 5 3 2 8 22 9 1 1 12 2 3 5 7 9 2 9 4 6 8 3样例输出1
30样例输出2
10 40 2 1 5 3 2 8 27 9 1 1 12 2 3 5 7 9 2 9 4 6 8 3样例输出2
36数据范围
对于30%的数据，有 n≤20,m=1n≤20,m=1
对于100%的数据
1≤K≤n≤200,1≤K≤n≤200,
1≤t≤2000,1≤t≤2000,
1≤m≤20,1≤m≤20,
1≤ai,bi≤10001≤ai,bi≤1000
代码:
#include <bits/stdc++.h>
using namespace std;
int n;
int t,m,k;
int a[205];
int b[205];
int dp[205][2005][25];
int main(){
cin>>n;
cin>>t>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=0;i<=t;i++){
dp[0][i][0]=0;
}
for(int i=1;i<=n;i++){
if(i==k){
m++;
}
for(int j=0;j<=t;j++){
for(int kk=0;kk<=m;kk++){
if(j<a[i]){
if(kk==0){
continue;
}
dp[i][j][kk]=min(dp[i][j][kk],dp[i-1][j][kk-1]);
}
else{
if(kk==0){
dp[i][j][kk]=min(dp[i][j][kk],dp[i-1][j-a[i]][kk]+b[i]);
}
else{
dp[i][j][kk]=min(dp[i-1][j][kk-1],dp[i-1][j-a[i]][kk]+b[i]);
}
}
}
}
}
cout<<dp[n][t][m+1];
return 0;
}