本文共 1247 字，大约阅读时间需要 4 分钟。

题目大意：

       道路上有n个显示器，让你选择三个显示器，每个显示器都有显示字体的大小，和费用，你需要租三个显示器，每个显示器显示字体的大小，逐渐递增，然后让他们花费最小。

题解：

法①：最开始的想法就是三重循环暴力，但是肯定会T

        后来明白了，换一种暴力姿势就可以了，暴力中间的显示器选哪个，然后在0-i中找可以的最小的第1个显示器，在i+1-n中找可以的最小的第3个显示器，这样就是 的暴力，就是把其中两层循环，循环本是相乘的形式，变成了相加的形式

#include
   
    #include
    
     using namespace std;#define ll long long#define INF 4000000000060000000ll s[3010],c[3010];int main(){    int n;    cin>>n;    for(int i=1;i<=n;++i)        cin>>s[i];    for(int i=1;i<=n;++i)        cin>>c[i];    ll ans=INF;    for(int i=1;i<=n;++i)    {        ll c1=INF,c2=INF;        for(int j=1;j
     
      s[i])                c2=min(c2,c[j]);        ans=min(ans,c1+c[i]+c2);    }    if(ans==INF)        ans=-1;    cout<
      
       <
      
     
    
   

法②：dp

dp[i][k]代表第i个物品作为三个中的第几个物品的最小花费

dp[i][k]=min(dp[j][k−1]+c[i]，dp[i][j])，其中：j<i且s[j]<s[i]。

#include
   
    #include
    
     using namespace std;#define ll long long#define INF 0x3f3f3f3fll s[3010],c[3010];ll dp[3010][5];int main(){    int n;    cin>>n;    for(int i=1;i<=n;++i)        cin>>s[i];    for(int i=1;i<=n;++i)        cin>>c[i];    memset(dp,INF,sizeof(dp));    for(int i=1;i<=n;++i)        dp[i][1]=c[i];    //dp[i][j]是第i个物品作为3个中的第几个的值    for(int i=1;i<=n;++i)    {        for(int k=2;k<=3;++k)        for(int j=1;j
    
   

转载地址：http://hzfgf.baihongyu.com/