題目來自建造基地
#include <stdio.h>#include <string.h>#include <limits.h>#include <iostream>using namespace std;long long dp[10010];long long ans;int A[110];int B[110];int N,M,K,T;long long min(long long a,long long b){ return a>b?b:a;}void changeT(){ for (int i = 1; i <=M; ++i) { B[i]/=T; }}int main(){ int qnum; scanf("%d",&qnum); while (qnum--){ ans=0; int flag= true; scanf("%d%d%d%d",&N,&M,&K,&T); for (int j= 1; j <=M ; ++j) { scanf("%d",A+j); } for (int k = 1; k <=M ; ++k) { scanf("%d",B+k); } for (int i = 0; i <N; ++i) { for (int k = 0; k <10010 ; ++k) { dp[k]=INT_MAX; } dp[0]=0; for (int j = 1; j <=M ; ++j) { for (int m =0; m<=K; ++m) { if(m+B[j]>K){ dp[K]=min(dp[K],dp[m]+A[j]); } else{ dp[m+B[j]]=min(dp[m+B[j]],dp[m]+A[j]); } } } if(dp[K]==INT_MAX){ flag= false; break; } ans+=dp[K]; changeT(); } if(!flag){新聞熱點
疑難解答
