洛谷：P5858 「SWTR-03」Golden Sword（dp，提高+/省選-）

題目：

分析：還好堅持著想了下去，題目放在這個題單，我想到的是在揹包問題上進行一定修改的dp。

僅僅對狀態轉移附近的程式碼進行修改就可以啦。

程式碼：

#include<bits/stdc++.h>
using namespace std;
long long A[5505][5505];//dp 
int B[5505];// 原始資料 
int m,w,s;// 原料總數 容納max  取max 
int main()
{
 for(int i=0;i<5505;i++) for(int j=0;j<5505;j++) A[i][j]=-(1<<30);
 cin>>m>>w>>s;
 for(int i=1;i<=m;i++) cin>>B[i];
 //初始化使用第一種材料   值為B[1]
 for(int i=1;i<5505;i++) A[1][i]=B[1];
 for(int i=2;i<=m;i++)
 for(int j=1;j<=w;j++)
 {
  for(int k=0;k+j<=w && k<s;k++)
  {
   A[i][j]=max(A[i][j],A[i-1][j+k]+min(i,j)*B[i]);
  }
  if(j==1) continue;
  A[i][j]=max(A[i][j],A[i-1][j-1]+min(i,j)*B[i]);
 }
 for(int i=1;i<=m;i++)
 {
 // for(int j=1;j<=w;j++) cout<<A[i][j]<<' ';
 // cout<<endl;
 }
 long long minn=A[m][1];
 for(int i=1;i<=w;i++)
 {
  minn=max(minn,A[m][i]);
 }
 cout<<minn;
}

結果雖然不咋地，但自己深入思考了，這個題也很好的，哈哈哈哈！！！