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

POJ5115-区间DP

热度:94   发布时间:2024-01-18 01:09:13.0
//区间DP
//DP[i][j]表示杀死(i,j)区间的狼能受到的最小伤害
//区间长度从1开始扩大
//状态转移方程:边界:DP[i][i] = a[i] + b[i-1] + b [i+1] ;
//              其他:DP[i][j] = min(DP[i][k-1] + a[k] + DP[k+1][j] ) + b[i-1] + b [j+1] ;
//k表示区间中杀死狼k
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std ;
#define MAX 205
#define N 0x3f3f3f3f
int a[MAX] , b[MAX] ;
int num ;
int DP[MAX][MAX] ;
void dp()
{int mini , j ;for(int i = 1 ; i <= num ; i ++)DP[i][i] = a[i] + b[i-1] + b [i+1] ;for(int t = 1 ; t < num ; t ++){for(int i = 1 ; i <= num ; i ++){j = i + t ;if(j > num) j = num ;mini = N ;for(int k = i ;k <= j ; k ++){if(DP[i][k-1]+a[k]+DP[k+1
  相关解决方案