文章目錄

• 題目描述
• 解析
• 代碼
• thanks for reading!

題目描述

一代爐石的眼淚啊

解析

用dp[i][j]表示i與j之間的全部消掉（不含兩端）的最小花費
然后枚舉中間最后殺死的狼就行了
本題沒有一次AC，因為一開始dp定義成了包含兩端，然后因為還受再外面的影響，寫的很亂
一次不成后經過思考，啊哈！ 正解思路就誕生了
所以尋找適用與題目的dp定義非常重要
正如之前的積木消消樂一樣

代碼

#include<bits/stdc++.h> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int N=600; const int M=2e6+100; int m,n; ll dp[N][N];//dp[i][j]:把i與j之間的全部消掉（不含兩端） int a[N],b[N],h[N],x; int seil(int x,int y){return x%y==0?x/y:x/y+1; } ll find(int st,int ed){if(dp[st][ed]) return dp[st][ed];if(st==ed-1) return 0;ll ans=2e17;for(int i=st+1;i<ed;i++){ans=min(ans,find(st,i)+find(i,ed)+seil(h[i],x)*(a[i]+b[st]+b[ed]));//枚舉最后消掉的狼 }return dp[st][ed]=ans; } int main(){scanf("%d%d",&n,&x);for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&h[i]);printf("%lld",find(0,n+1));return 0; }

thanks for reading!

總結

以上是生活随笔為你收集整理的不止代码：恐狼后卫（ybtoj-区间dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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