自己搭建网站做网上商城,南京推广公司,重庆网站建设论坛,小时的网站建设文章目录题目描述解析代码thanks for reading!题目描述 一代炉石的眼泪啊
解析
用dp[i][j]表示i与j之间的全部消掉#xff08;不含两端#xff09;的最小花费 然后枚举中间最后杀死的狼就行了 本题没有一次AC#xff0c;因为一开始dp定义成了包含两端#xff0c;然后因为…
文章目录题目描述解析代码thanks for reading!题目描述 一代炉石的眼泪啊
解析
用dp[i][j]表示i与j之间的全部消掉不含两端的最小花费 然后枚举中间最后杀死的狼就行了 本题没有一次AC因为一开始dp定义成了包含两端然后因为还受再外面的影响写的很乱 一次不成后经过思考啊哈 正解思路就诞生了 所以寻找适用与题目的dp定义非常重要 正如之前的积木消消乐一样
代码
#includebits/stdc.h
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N600;
const int M2e6100;
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%y0?x/y:x/y1;
}
ll find(int st,int ed){if(dp[st][ed]) return dp[st][ed];if(sted-1) return 0;ll ans2e17;for(int ist1;ied;i){ansmin(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 i1;in;i) scanf(%d%d%d,a[i],b[i],h[i]);printf(%lld,find(0,n1));return 0;
}
thanks for reading!
