題目描述

?最近卡斯丁狗和他的好基友Tomcat在玩《我的世界》這款游戲。在游戲中玩家可以用各種材料搭建房屋，制造鐵路線，制造炸彈，晚上還可以打僵尸等等。然而在這之前最最重要的就是挖礦。這天卡斯丁狗背著一個最多能裝重量為 n 的背包去礦洞里挖礦。從洞口看礦洞是一個深度為d等腰RT超級賽亞三角形，每個坐標點都有礦（如圖）。洞口在三角形的最頂端，坐標為（1,1）。由于卡斯丁狗開掛，他只想從坐標為（x，y）的點走到坐標為（x+1，y）或者（x+1，y+1）的點，并且每經過一個點他可以選著挖或者不挖這個點的礦。問卡斯丁狗最多能背多少礦回家。

輸入

第一行輸入n，d。

接下來d行第i行輸入i個數，表示礦的重量。

輸入為小于300大于0。

輸出

?輸出最大能帶走的礦。

樣例輸入

100 3 99 1 99 100 1 44

樣例輸出

100 代碼： #include<bits/stdc++.h> using namespace std; #define maxn 305 int dp[maxn][maxn][maxn]; int n,b; int main(){while(~scanf("%d %d",&n,&b)){memset(dp,0,sizeof(dp));int mx=0;int x;for(int i=1;i<=b;i++){for(int j=1;j<=i;j++){scanf("%d",&x);for(int k=x;k<=n;k++){dp[i][j][k]=max(max(dp[i-1][j-1][k],dp[i-1][j][k]),max(dp[i-1][j-1][k-x]+x,dp[i-1][j][k-x]+x));}mx=max(mx,dp[i][j][n]);}}cout<<mx<<endl; } }

總結

以上是生活随笔為你收集整理的zcmu——1601: 卡斯丁狗去挖矿（01背包-三维数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。