Problem 1538 - B - Stones II 贪心+DP

还是给你石头n枚，每一枚石头有两个值a和b，每取一个石头，除了这块石头其余所有的石头的a就都减去这个石头的b，问你取了的石头的a的总和最大可以为多少？

先按B从大到小排序

然后DP:

取的话:dp[i][j]=dp[i-1][j-1]+a[i]-b[i]*(j-1) 注意是j-1

不取的话:dp[i][j]=dp[i-1][j];

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 1100

struct Inf

{

    int a,b;

}save[Maxn];

LL dp[Maxn][Maxn];

int n;

LL Max(LL a,LL b)

{

    return a>b?a:b;

}

bool cmp(struct Inf a,struct Inf b)

{

    return a.b>b.b;

}

int main()

{

   //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(scanf("%d",&n)&&n)

   {

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

           scanf("%lld%lld",&save[i].a,&save[i].b);

       sort(save+,save+n+,cmp);

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

                dp[i][]=;

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

       {

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

                dp[i][j]=max(dp[i-][j-]+save[i].a-save[i].b*(j-),dp[i-][min(j,i-)]);

               //dp[i][j]=Max(dp[i-1][j],dp[i-1][j+1]+save[i].a-save[i].b*j);

       }

       LL ans=;

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

        ans=max(ans,dp[n][i]);

       printf("%lld\n",ans);

   }

   return ;

}

另一种状态方程:

dp[i][j]:表示第i堆后还要选j堆能达到的最大值。

dp[i][j]=max(dp[i-1][j],dp[i-1][j+1]+a[i]-b[i]*j) ; //要么选要么不选

//#include<CSpreadSheet.h>

#include<iostream>

#include<cmath>

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<string>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#include<ctime>

#include<bitset>

#define eps 1e-6

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define ll __int64

#define LL long long

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

#define M 1000000007

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define Maxn 1100

struct Inf

{

    int a,b;

}save[Maxn];

LL dp[Maxn][Maxn];

int n;

LL Max(LL a,LL b)

{

    return a>b?a:b;

}

bool cmp(struct Inf a,struct Inf b)

{

    return a.b<b.b;

}

int main()

{

   //freopen("in.txt","r",stdin);

   //freopen("out.txt","w",stdout);

   while(scanf("%d",&n)&&n)

   {

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

           scanf("%lld%lld",&save[i].a,&save[i].b);

       memset(dp,-INF,sizeof(dp)); //无效状态

       //printf("%d\n",dp[1][1]);

       sort(save+,save+n+,cmp);  //顺序 肯定对b从小到大比较优

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

            dp[][i]=;

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

       {

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

               dp[i][j]=Max(dp[i-][j],dp[i-][j+]+save[i].a-save[i].b*j);

       }

       printf("%lld\n",dp[n][]);

   }

   return ;

}

巴特西

Problem 1538 - B - Stones II 贪心+DP

最新文章

热门文章