洛谷 P1412 经营与开发

/*

粘一下开始写的暴力吧 虽然没啥价值

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#define maxn 100010

using namespace std;

int n,type[maxn];

double k,c,w,v[maxn],ans;

void Dfs(int p,double t,double m)

{

    if(p==n+)

      {

          ans=max(ans,m);

          return;

      }

    if(type[p]==)Dfs(p+,t*(-double(k/100.0)),m+v[p]*t);

    if(type[p]==)Dfs(p+,t*(+double(c/100.0)),m-v[p]*t);

    Dfs(p+,t,m);

}

int main()

{

    freopen("exploit.in","r",stdin);

    freopen("exploit.out","w",stdout);

    cin>>n>>k>>c>>w;

    for(int i=;i<=n;i++)

      cin>>type[i]>>v[i];

    Dfs(,w,);

    printf("%.2f\n",ans);

    return ;

}

/*

似乎不是dp题 因为前面的决策影响后面的决策 具有后效性

然而他就是dp题 - -

正难则反 我们发现后面的决策对前面的没有影响

但是显然后面的用到前面的决策来确定钻头能力值

我们不先计算出前面的 无法确定后面的能力值

仔细看题目的话 我们会发现前面的对后面的影响只是乘一个数值

那么我们可以先不乘 反着跑 到了前面在乘

对于每一个i 有选或者不选两种情况

 （1）资源型：如果选了 那么金钱数变大 能力值变小 对后面的影响就是能力值*k 然后+钱

              我们假设每个i的能力值为1*w

              有 f[i]=max(f[i+1],f[i+1]*k+v[i]*w);

 （2）维修型：如果选了 那么金钱数变小 能力值变大 对后面的影响就是能力值*c 然后-钱

              同上假设每个i的能力值为1*w

              有 f[i]=max(f[i+1],f[i+1]*c-v[i]*w);

注意并不是得到的f[1]就是最优解 所以对所有的f取大

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#define maxn 100010

using namespace std;

int n,type[maxn];

double k,c,w,f[maxn],v[maxn],ans;

int main()

{

    cin>>n>>k>>c>>w;

    for(int i=;i<=n;i++)

      cin>>type[i]>>v[i];

    k=(-k)/100.0;c=(+c)/100.0;

    for(int i=n;i>=;i--)

      {

          if(type[i]==)

          f[i]=max(f[i+],f[i+]*k+v[i]*w);

          if(type[i]==)

          f[i]=max(f[i+],f[i+]*c-v[i]*w);

          ans=max(ans,f[i]);

      }

    printf("%.2f\n",ans);

    return ;

}