和田做网站的联系电话,fn网站不是做那么好吗,wordpress js漏洞,口碑好的黄石网站建设Food Delivery ZOJ - 3469 区间DP的一道好题。
在这道题里#xff0c;无非就是从出发点向左走到x1再向右走到有y1#xff0c;再向左走到x2#xff0c;再向右走到y2.。。。这样#xff0c;一直将所有的顾客遍历完。
显然#xff0c;起点这个点是非常特殊的一个点#xf… Food Delivery ZOJ - 3469 区间DP的一道好题。
在这道题里无非就是从出发点向左走到x1再向右走到有y1再向左走到x2再向右走到y2.。。。这样一直将所有的顾客遍历完。
显然起点这个点是非常特殊的一个点我们姑且也把它算作一名顾客那么这名顾客的愤怒值设置为0。
然后定义dp[x][y][0]表示区间遍历完[x,y]了并且当前停留在x位置上将对最终的愤怒值之和造成的贡献。
定义dp[x][y][1]表示遍历完区间[x,y]并且当前停留在y位置上将对最终的愤怒之和造成的贡献。
从上面我们的讨论中可以发现[x,y]一定是包含起始点S的不然这个区间将没有意义。
我们可以得到状态转移的方程 我们没有在这里就把V乘进去而是在最后才把V考虑进去
dp[i][j][0] min(dp[i][j][0],dp[i1][j][0] (Ns[i1].x - Ns[i].x)*(sum[N1] - (sum[j] - sum[i]))); dp[i][j][0] min(dp[i][j][0],dp[i1][j][1] (Ns[j].x - Ns[i].x)*(sum[N1] - (sum[j] - sum[i]))); dp[i][j][1] min(dp[i][j][1],dp[i][j-1][1] (Ns[j].x - Ns[j-1].x)*(sum[N1] - (sum[j-1] - sum[i-1]))); dp[i][j][1] min(dp[i][j][1],dp[i][j-1][0] (Ns[j].x - Ns[i].x)*(sum[N1] - (sum[j-1] - sum[i-1])));
以上的状态转移方程就相当于把区间扩大了一位数字贡献增加的值。
我看很多题解的时候没有明确说明dp表示的是对于答案的贡献值所以没能充分的理解。
反思这个动态规划的题目有点特别就是说dp代表的东西不能形成一个类似的独立的子问题而仍然是刻画原问题的某个性质的一部分这里我觉得是与其他一些dp不同的地方。 #include cstdio
#include iostream
#include algorithm
#include cstring
using namespace std;
int N,V,X;
const int INF 1e9;
const int MAX 1005;
struct node{int x,val;friend bool operator(node n1,node n2){return n1.x n2.x;}
}Ns[MAX];
int dp[MAX][MAX][2];
int sum[MAX];
int main(){while(~scanf(%d%d%d,N,V,X)){memset(dp,0,sizeof(dp));for(int i 1;i N;i){int x,b;scanf(%d%d,x,b);Ns[i].x x;Ns[i].val b;}Ns[N1].x X;Ns[N1].val 0;sort(Ns1,NsN2);int s 0;while(Ns[s].x ! X);for(int i 1;i N1;i) sum[i] sum[i-1] Ns[i].val;for(int i 1;i N1;i){for(int j 1;j N1;j){dp[i][j][0] dp[i][j][1] INF;}}dp[s][s][0] dp[s][s][1] 0;for(int i s;i 0;i--){for(int j s;j N1;j){if(i j) continue;dp[i][j][0] min(dp[i][j][0],dp[i1][j][0] (Ns[i1].x - Ns[i].x)*(sum[N1] - (sum[j] - sum[i])));dp[i][j][0] min(dp[i][j][0],dp[i1][j][1] (Ns[j].x - Ns[i].x)*(sum[N1] - (sum[j] - sum[i])));dp[i][j][1] min(dp[i][j][1],dp[i][j-1][1] (Ns[j].x - Ns[j-1].x)*(sum[N1] - (sum[j-1] - sum[i-1])));dp[i][j][1] min(dp[i][j][1],dp[i][j-1][0] (Ns[j].x - Ns[i].x)*(sum[N1] - (sum[j-1] - sum[i-1])));}}int ans min(dp[1][N1][0],dp[1][N1][1]);printf(%d\n,ans*V);}return 0;
}