[UVA] 812 - Trade on Verweggistan

題意:
輸入數筆測資，
輸入N個數列，每個數列第一個數字表示該數列的元素數量，
每個數列的每個數字表示以多少錢進購產品，每個產品再以10元賣給荷蘭，
所以要求的是最大利潤，
以及要進購多少產品的前10個可能的值。
進購得產品是有依序的，也就是說要先進購第一個產品才能進購第二個產品。

測資間要空行，最後一筆測資後面不需要空行。

--------------------------------------------------

方法:
先將讀進來的每個數字改為進購第 i 個產品可得的利潤，
進而求出該數列最大可得利潤，
最後將每個數列的最大利潤相加總就是題目的第一個所求。
可以得知每個數列的最大利潤是在進購多少產品，
所以可以先記錄起來，
例如:
第一個數列有三個6,11,9，分別在進購第1個,第2個,第3個的利潤是
4,3,4
表示在連續進購 1 個或連續進購 3 個產品時可以得到最大利潤4，
那就將1 和 3記錄起來當記錄值，表示該數列可以進購1或3個都可以得到最大利潤，
最後用遞迴將每個數列的紀錄值去做組合，最後排序後輸出不重複的前10個數字。


注意!當最大利潤是0時，進購的產品數量也可以是0。

--------------------------------------------------

/* 20150923
 * hanting
 * UVa 812 - Trade on Verweggistan
 * C++
 */
#include <iostream>
#include <vector>
#include <cstring> //memset
#include <algorithm> //sort
#include <set>
using namespace std;
void DFS(vector<int> *vec,int N,set<int> &Set,int sum,int cur)
{
    if(cur==N)
    {
        Set.insert(sum);
    }
    else
    {
        for(int i=0;i<vec[cur].size();i++)
        {
            int tmp=vec[cur][i];
            DFS(vec,N,Set,sum+tmp,cur+1);
        }
    }
}
int main()
{
    int N;
    int caseN=0;
    while(cin>>N and N)
    {
        vector<int> profit[N];
        vector<int> NumToBuy[N];
        int Max[N];
        memset(Max,0,sizeof(Max));
        int MaximumProfit=0;
        for(int i=0;i<N;i++)
        {
            int numN;
            cin>>numN;
            for(int j=0;j<numN;j++)
            {
                int num;
                cin>>num;
                profit[i].push_back(10-num);
                if(j) profit[i][j]+=profit[i][j-1];
                Max[i]=max(Max[i],profit[i][j]);
            }
            if(Max[i]==0) NumToBuy[i].push_back(0);
            for(int j=0;j<numN;j++)
            {
                if(profit[i][j]==Max[i])
                    NumToBuy[i].push_back(j+1);
            }
            MaximumProfit+=Max[i];
        }
        set<int> Set;
        DFS(NumToBuy,N,Set,0,0);

        if(caseN) cout<<endl;
        cout<<"Workyards "<<++caseN<<endl;
        cout<<"Maximum profit is "<<MaximumProfit<<"."<<endl;
        cout<<"Number of pruls to buy:";
        int cnt=0;//輸出前10個即可
        for(set<int>::iterator it=Set.begin();it!=Set.end() and cnt<10;++it,cnt++)
        {
            cout<<" "<<*it;
        }
        cout<<endl;

    }
    return 0;
}