[ACM]发工资解决方案

2012-02-19

[ACM]发工资发工资Time Limit:3000MSMemory Limit:65536KTotal Submit:1 Accepted:1Description由于训练强

[ACM]发工资
发工资

Time Limit:3000MS Memory Limit:65536K
Total Submit:1 Accepted:1

Description

由于训练强度很大，NWPU ACM 一队现在只剩下两个人了 :-( 。于是Mr. Wang决定开始给队员发工资，而且是以每个小时一次的高频率来发工资，每次工资金额不少于 0 元，不多于 2,000,000,000 元。

队中仅剩的两名队员，beiju同学和 canju同学，想出了一种特别的分配工资方法。

他们不是将工资平分，而是轮流领取。该当领工资的人可以选择跳过一个或多个小时的工资，而领取后面的工资。跳过的工资会归还Mr. Wang，以后也不能被任何人领取了。

比如，最近 5 个小时工资的发放金额为：100， 200， 800， 50， 150 ；轮到 beiju 同学领工资。那beiju同学很可能选择跳过前两个小时的工资，而领取第三小时的工资800元，之后canju同学则会选择跳过50而领取150元。

这样一来，领工资就成为了一个 beiju同学和 canju同学之间的博弈问题。

现在他们知道一共要发 N (1 <= N <= 700,000) 次工资，每次发放的金额也已知。beiju 和 canju 都是训练有素的ACMer，当然都会采取使自己领到的工资总数最多的策略。假设beiju同学先领取。

如果你想加入 ACM 队，请快速计算出两人各会领到多少钱。

Input

第1行有一个数字：N

第2行到第N+1行，每行一个整数，表示该次发放的工资金额

Output

仅一行，两个整数，用一个空格隔开，分别表示beiju同学和canju同学获得的工资总量。

Sample Input

6
17
5
9
10
3
8

Sample Output

27 17

Hint

注意输出要以“\n”结尾。

当心使用32位整数类型存储导致溢出。

[解决办法]

C/C++ code

 124.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <vector>using namespace std;typedef unsigned int size_type;int _tmain(int argc, _TCHAR* argv[]){    size_type n;    n = 6;    vector<__int64> v;    vector<pair<size_type,size_type> > vNum;    v.clear();    v.push_back(3);    v.push_back(11);    v.push_back(9);    v.push_back(10);    v.push_back(3);    v.push_back(8);    v.push_back(0);//最后标号n记录一个0数据的无效数据,防止数据溢出使用.    vNum.clear();    vNum.resize(n + 1 ,pair<size_type,size_type>(n,n));    vNum[n - 1].first = n - 1;//记录最后只有一个元素,记录当前最佳选择    vNum[n - 1].second = n;//已经没有选择了.    vector<__int64> vSum;    vSum.clear();    vSum.resize(n + 1,0);    for(size_type x = n - 1;;-- x){        if(vSum[vNum[x + 1].first] < v[x] + vSum[vNum[x + 1].second]){//如果选择跳过 没 选择当前的 好则选择当前            vSum[x] = v[x] + vSum[vNum[x + 1].second];            vNum[x].first = x;//当前最好选择            vNum[x].second = vNum[x + 1].first;//对方接下来最好的选择        }        else{//跳过好过选择当前的,            vNum[x].first = vNum[x + 1].first;            vNum[x].second = vNum[x + 1].second;            vSum[x] = vSum[vNum[x + 1].first];        }        if(x == 0)            break;    }cout<<vSum[0]<<endl;cout<<vSum[vNum[0].second]<<endl;for(size_type x = 0; x < n;){    if(vNum[x].first == n)//无效编号判断        break;    cout<<v[vNum[x].first]<<" ";//最先现在的人选择的编号    x = vNum[x].second;    if(vNum[x].first == n)//无效编号判断        break;    cout<<v[vNum[x].first]<<endl;    x = vNum[x].second;}cout<<endl;    return 0;}
[解决办法]
s1 = 8 ,s2 = 0, num=1 ,temp;
int b[7]={6,17,5,9,10,3,8};
int a=7;//回调时使用
Again:
for(int c = a;c>0;c--)
 if(s2+b[c]>=s1)
 {
   temp = s1;
   s1 = s2+b[c];
   s2 = temp;
   num++;
 }
if(num%2==1)//因为两人轮流领取,所以领取次数为双数
{
 a--;
 num=1;
 goto Again;
}
[解决办法]
为什么可以倒着推到，就像3楼说的，属于博弈论，给个简单的代码吧（和12楼的很像）。
分不重要，LZ平均分了就可以。

C# codeusing System;namespace CsdnTest{    class Program    {        static void Main(string[] args)        {            int[] salary = new int[] { 6, 17, 5, 9, 10, 3, 8 };            long S1 = 0, S2 = 0, tempValue = 0;            for (int i = salary.Length - 1; i >= 0; i--)            {                if (salary[i] + S2 >= S1)                {                    tempValue = S2;                    S2 = S1;                    S1 = tempValue + salary[i];                }            }            Console.WriteLine("{0} {1}", S1, S2);        }    }}

热点排行

软件架构设计

[ACM]发工资解决方案