当前位置: 代码迷 >> 综合 >> UVA10154-区间DP
  详细解决方案

UVA10154-区间DP

热度:30   发布时间:2024-01-18 01:05:45.0

题意:给出一些乌龟的重量和力量,求这些乌龟能叠出的龟塔的最大高度

题解:区间DP,dp[i][j]代表前i只乌龟叠j层的最小重量,从层数开始扩展转移,先求从1-n每个区间叠一层的质量,再求叠两层,以此类推

       状态转移方程:if(turtle[i].strength >= dp[i-1][j-1])
dp[i][j] = min(dp[i-1][j] , dp[i-1][j-1]+turtle[i].weight) ;
else
dp[i][j] = dp[i-1][j] ;

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std ;
#define MAX 5700
#define INF 0x3f3f3f3f
int dp[MAX][MAX] ;
struct Node
{int weight ;int strength ;
}turtle[MAX];
bool comp(const struct Node &x ,const struct Node &y)
{//if(x.strength == y.strength) return x.weight < y.weight ;return x.strength < y.streng
  相关解决方案