DP之花店橱窗布置

2019/7/25 8:26:15 人评论 次浏览 分类:学习教程

原文链接:http://www.cnblogs.com/riasky/p/3435791.html

题目:https://www.smartoj.com/p/1286


分析:花瓶是有序的,花也是有序的,这就保证了有序性,从而满足子解的全局最优,和无后效性.假设dp[i][j]表示前i

花,放在前j个花瓶里的最优值.


则有: 


那么经过优化后得到:



 

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 105;
const int INF = 1<<30;

int a[N][N];
int dp[N][N];
bool path[N][N];

void Print(int i,int j)
{
    if(i == 0) return;
    if(path[i][j])
    {
        Print(i-1,j-1);
        printf("%d ",j);
    }
    else Print(i,j-1);
}

int main()
{
    int F,V;
    while(~scanf("%d%d",&F,&V))
    {
        memset(path,0,sizeof(path));
        for(int i=1;i<=F;i++)
            for(int j=1;j<=V;j++)
                scanf("%d",&a[i][j]);
        for(int i=1;i<=F;i++)
            for(int j=0;j<=V;j++)
                dp[i][j] = -INF;
        for(int i=1;i<=F;i++)
        {
            for(int j=i;j<=V && i <= i + F;j++)
            {
                if(dp[i-1][j-1] + a[i][j] <= dp[i][j-1])
                    dp[i][j] = dp[i][j-1];
                else
                {
                    dp[i][j] = dp[i-1][j-1] + a[i][j];
                    path[i][j] = 1;
                }
            }
        }
        printf("%d\n",dp[F][V]);
        Print(F,V);
        puts("");
    }
    return 0;
}


 

 

转载于:https://www.cnblogs.com/riasky/p/3435791.html

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?

    立即查看