武大网赛预赛 Problem 1538 - B

武大网赛预赛 Problem 1538 - B - Stones II

阅读量：2494 次

发布时间：2019-05-11

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

http://acm.whu.edu.cn/land/problem/detail?problem_id=1538

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

解题思路：

把石头按照b从大到小排列，因为越大的越要倒数（放在后面）取，就越要排在数组前面。关于这一点，昨天晚上又仔细想了一遍。首先如果两个b相等，那么谁前谁后没关系，因为减去的都是b，通过dp可以取出其中a大的那种情况。然后就是一个01背包。

因为第k次取会影响到第k+1次取，所以想到从后往前取。先取倒数第1个，再取倒数第二个，这样得到状态转移方程：

dp[i][j] = max( dp[i-1][j], dp[i-1][j-1] + node[i].a - node[i].b * (j-1) )

dp[i][j] 表示前i个里面取j个时的a最大总和。

用前i-1个里面取j个时的最大值的情况，比较前i-1个里面取j-1个的最大值加上把第i个放到倒数第j个取的情况。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define FOR(a,b,c) for (int a=b,_c=c;a<=_c;a++)#define FORD(a,b,c) for (int a=b;a>=c;a--)#define REP(i,a) for(int i=0,_a=(a); i<_a; ++i)#define REPD(i,a) for(int i=(a)-1; i>=0; --i)#define pb push_back#define mp make_pair#define fi first#define se second#define sz(a) int(a.size())#define reset(a,b) memset(a,b,sizeof(a))#define oo 1000000007using namespace std;typedef long long ll;typedef pair
                  
                    pii;const int maxn = 1010;pii node[maxn];int dp[maxn][maxn];bool cmp(const pii &x, const pii &y){ return x.se > y.se;}int main(){// freopen("data.in", "r", stdin); int n, ans; while(scanf("%d", &n) != EOF && n != 0) { FOR(i, 1, n) scanf("%d%d", &node[i].fi, &node[i].se); sort(node+1, node+n+1, cmp); FOR(i, 0, n) dp[i][0] = 0; FOR(i, 1, n) FOR(j, 1, i) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + node[i].fi - node[i].se * (j-1)); } ans = 0; FOR(i, 1, n) ans = max(ans, dp[n][i]); printf("%d\n", ans); } return 0;}

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

你可能感兴趣的文章

期货市场技术分析07_摆动指数和相反意见理论