FJNU1196 汪老司机

#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main(){ int maxn=10005;//注意数组的边界 int T; cin>>T; while(T--){ int n,k; cin>>n>>k; long long array[maxn][3];//将两条路定义为一个二维数组 long long dp[maxn][15][3];//定义一个三维数组，第二位表示在换了J次路后的耗油量 int i,j; for(j=1;j<=2;j++) for(i=1;i<=n;i++) cin>>array[i][j]; memset(dp,0x7f,sizeof(dp));//初始化DP,且初始值要够大 dp[1][0][1]=array[1][1];//开始选择第一条路不需要进行换路，直接赋值 dp[1][0][2]=array[1][2]; for(i=2;i<=n;i++){ dp[i][0][1]=dp[i-1][0][1]+array[i][1]; //表示第一次换路后的情况 dp[i][0][2]=dp[i-1][0][2]+array[i][2]; for(j=1;j<=min(i,k);j++){ //接下来遍历所有换路不换路的情况 dp[i][j][1]=min(dp[i-1][j][1],dp[i-1][j-1][2])+array[i][1]; dp[i][j][2]=min(dp[i-1][j][2],dp[i-1][j-1][1])+array[i][2]; } } long long ans=100000000000000; for(j=0;j<=k;j++) ans=min(ans,min(dp[n][j][1],dp[n][j][2]));//由于题目给的最大耗油量够大，必须与题给的最大耗油量进行比较取最小值 cout<<ans<<endl; } return 0; }