题目链接HDU-5115
思路：
这个是一个DP的题目，原因是前一刻的状态会影响到后一刻的状态，所以我从DP的角度来思考这道题的解法，我想的是假如【i，j】的狼已经被吃完了，那么接下来【i-1，j+1】的狼就会受到【i，j】的影响，只要判断【i，j+1】和【i-1，j】哪个区间段再加上对应加上的狼的BUFF需求即可，但这还不够（会WA的嘛，肯定还有BUG），那么BUG在哪呢？我们目前确定的是从中心区域直接向外拓展时候的状况，但是，假如子区间内有更优解，我们却丢失了它怎么办，所以，我们需要完善。
优化：对于【i，j】这个区间，我们还得更新其子区间，我们设一个k从【i， j-1】这个区间段一一遍历，那么我们杀狼【i，j】可以看作杀狼【i，k】+【k+1，j】，但是作为dp，我们在改变其状态不能忘记先决条件也已经改变了，我们先杀了【i，k】的狼，那么杀【k+1，j】的狼，它的BUFF就变了，杀第k+1个狼的时候，它的左BUFF就不是k了，而是变成了i-1，因为【i，k】狼已死。
DP状态转移方程：
最先的时候先是：dp[i][j]=min(dp[i+1][j] + a[i-1] + a[j+1], dp[i][j-1] + a[i-1] + a[j+1]);
dp[i][j]=min(dp[i][j], dp[i][k] + dp[k+1][j] - a[k] + a[i-1])。
完整代码：
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #define lowbit(x) ( x&(-x) ) #define pi 3.9793 #define e 2.9045 using namespace std; typedef long long ll; const int maxN=205; int N, sum; int dp[maxN][maxN], a[maxN]; int main() { int T; scanf("%d", &T); for(int Cas=1; Cas<=T; Cas++) { scanf("%d", &N); sum=0; memset(dp, 0, sizeof(dp)); memset(a, 0, sizeof(a)); for(int i=1; i<=N; i++) { int e1; scanf("%d", &e1); sum+=e1; } for(int i=1; i<=N; i++) scanf("%d", &a[i]); for(int i=1; i<=N; i++) { for(int j=i; j>=1; j--) { dp[j][i]=min(dp[j+1][i] + a[j-1] + a[i+1], dp[j][i-1] + a[i+1] + a[j-1]); for(int k=j; k<=i-1; k++) { dp[j][i]=min(dp[j][i], dp[j][k] - a[k] + a[j-1] + dp[k+1][i]); } } } sum+=dp[1][N]; printf("Case #%d: %d\n", Cas, sum); } return 0; } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/28760.html