평행 사각형 최적화 (HDOJ 3506)
2451 단어 공부 하 다.
증명:http://baike.baidu.com/view/1985058.htm?fr=aladdin
이런 문 제 를 해결 하 는 대략적인 절 차 는:
상태 이동 방정식 dp [i] [j] = min {dp [i] [k - 1] + dp [k] [j]} + w [i] [j] (i<=k<=j)
평행 사각형 으로 최적화 하려 면 w [i] [j], dp [i] [j] 가 사각형 부등식 을 만족 시 키 는 지 증명 해 야 한다.
w [a, c] + w [b, d] < = w [b, c] + w [a, d] (a 볼록 사각형 부등식
또는 시 계 를 쳐 서 w [i] [j + 1] - w [i] i 에 관 한 표현 식 을 관찰 합 니 다. i 체감 에 관 해 서 는 w 가 돌출 사각형 의 부등식 을 만족 시 킵 니 다.
하면, 만약, 만약... w[i'][j]<=w[i][j'] i<=i'<=j<=j' 구간 포함 관계 단조
만약 w 가 사각형 부등식 과 구간 단조 로 운 관 계 를 동시에 만족 시 키 면 dp 도 사각형 부등식 을 만족시킨다.
일반적인 동적 계획 의 복잡 도 는 O (n ^ 3) 이 고 사각형 부등식 프로그램 에서 한 번 뛰 는 i 는 j 만 한 번 뛰 기 때문에 O (n ^ 2) 로 최적화 할 수 있 습 니 다.
상세 증명:
http://baike.baidu.com/view/1985058.htm?fr=aladdin
http://blog.csdn.net/lmyclever/article/details/6677683
전형 적 인 돌 합병 문제:http://blog.csdn.net/acdreamers/article/details/18039073
HDOJ2829
제목 의 대의: 길이 가 n 인 서열 을 정 하고 기껏해야 서열 을 m 단 으로 나 누 며 각 단락 의 서열 은 모두 가중치 가 있 으 며, 가중치 는 서열 내 두 개의 수 와 두 개의 곱 하기 합 이다. m < = n < 1000. 가중치 가 가장 작다.
상태 이동 방정식:
dp[c][i]=min(dp[c][i],dp[c-1][j]+w[j+1][i])
#include
#include
#include
using namespace std;
const int INF=1<<30;
const int MAXN=1000+10;
typedef long long LL;
LL dp[MAXN][MAXN];//dp[c][j] j c
int val[MAXN];
int w[MAXN][MAXN];//w[i][j] i j
int s[MAXN][MAXN];//s[c][j] j c
int sum[MAXN];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)break;
memset(s,0,sizeof(s));
memset(w,0,sizeof(w));
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;++i)
{
scanf("%d",&val[i]);
sum[i]+=sum[i-1]+val[i];
}
for(int i=1;i<=n;++i)
{
w[i][i]=0;
for(int j=i+1;j<=n;++j)
{
w[i][j]=w[i][j-1]+val[j]*(sum[j-1]-sum[i-1]);
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
dp[j][i]=INF;
}
}
for(int i=1;i<=n;++i)
{
dp[0][i]=w[1][i];
s[0][i]=0;
}
for(int c=1;c<=m;++c)
{
s[c][n+1]=n;//
for(int i=n;i>c;--i)
{
int tmp=INF,k;
for(int j=s[c-1][i];j<=s[c][i+1];++j)
{
if(dp[c-1][j]+w[j+1][i] 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
자바 두 수의 최대 공약수 구하 기 (세 가지 방법)자바 두 수의 최대 공약수 구하 기 (세 가지 방법) 1. 역법 전에 저도 몰 랐 습 니 다. 인터넷 에서 찾 아 봤 는데 0 과 0 이 아 닌 수의 약 수 는 모두 이 0 이 아 닌 숫자 입 니 다. 결실 2. 전...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
