IOI1999 花店橱窗布置

分析

动态规划法,用 表示用了 朵花,摆了 个花瓶的最大美学值 (不一定要摆第 个花瓶), 表示第 i 朵花摆第 个花瓶中最大的一个花瓶的美学值

处理 m 数组, DP,总复杂度 O(n^3).

代码

#include<iostream>

using namespace std;

int n,v,mx,mxn;
int a[101][101],f[101][101],m[101][101][101];
int pre[101][101];

void sol_print(int ni,int vi){if(!pre[ni][vi])return;
    sol_print(ni-1,pre[ni][vi]);
    cout<<pre[ni][vi]<<' ';}

int main(){cin>>n>>v;
    for(int i=1;i<=n;i++){for(int j=1;j<=v;j++){cin>>a[i][j];
            f[i][j]=0-999999;
        }
    }
    for(int i=1;i<=n&&i<=v;i++)f[i][i]=f[i-1][i-1]+a[i][i];
    for(int i=1;i<=n;i++){for(int j=i;j<=v;j++){m[i][j][j]=a[i][j];
            for(int k=j+1;k<=v;k++){if(m[i][j][k-1]>a[i][k])m[i][j][k]=m[i][j][k-1];
                else m[i][j][k]=a[i][k];
            }
        }
    }
    for(int i=1;i<=n;i++){for(int j=i;j<=v;j++){for(int k=i-1;k<j;k++){if(f[i][j]<f[i-1][k]+m[i][k+1][j]){f[i][j]=f[i-1][k]+m[i][k+1][j];
                    pre[i][j]=k;
                }
            }
        }
    }
    for(int j=1;j<=v;j++)if(f[n][j]>mx)mx=f[n][j],mxn=j;
    cout<<f[n][mxn]<<endl;
    sol_print(n,mxn);
    cout<<mxn;
    return 0;
}

 上一篇
CF10D LCIS CF10D LCIS
题意求两个串的最长公共上升子序列。 n,m<=500 分析用 表示 A 与 B 构成的以 为结尾的 LCIS 的长度: f[i][j]=\max_{k=0}^{j-1}\{f[i-1][k]+1\}
2018.10.01
下一篇 
[LuoguP1156] 垃圾陷阱 [LuoguP1156] 垃圾陷阱
一道很恶心的背包 DP 需要考虑很玄学的的细节 总之,要精心判断是否能转移,再转移 结合刷表法和填表法 详细的看 Luogu 题解去吧 #include<bits/stdc++.h> using namespace std; con
2018.10.01
  目录