BestCoder Round #91 1001 Lotus and Characters

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6011

題意：

Lotus有nn種字母，給出每種字母的價值以及每種字母的個數限制，她想構造一個任意長度的串。 定義串的價值為：第1位字母的價值*1+第2位字母的價值*2+第3位字母的價值*3…… 求Lotus能構造出的串的最大價值。（可以構造空串，因此答案肯定\geq 0≥0）

分析：

做這個題目的時候，第一感覺回溯算了，不用想，肯定T了。

#include <bits/stdc++.h>

using namespace std;

int n;
int val[30];
int cnt[30];
int len;

int dfs(int cur)
{
    int ans = 0;
    if(cur>=len+1) return 0;
    else
    {
        for(int i=0; i<n; i++)
        {
            if(cnt[i]>0)
            {
                cnt[i]--;
                ans = max(ans,(cur+1)*val[i]+dfs(cur+1));
                cnt[i]++;
            }
        }
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t);

    while(t--)
    {
        scanf("%d",&n);
        len = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&val[i],&cnt[i]);
            len+=cnt[i];
        }

        printf("%d\n",dfs(0));
    }
    return 0;
}

?

后來想DP，直覺告訴我，正權值的放后面。每次計算后面的數值，又不知道前面有多少位，怎么解決這個問題呢？

就類似于前綴和，寫一個后綴和，之前的位數不確定，怎么解決呢？

Ans[i] = Ans[i+1] + sum[i+1] +v[i];

狀態轉移就是多加了一遍后綴和，和首位。最后找一下最好的切割點。

其實這個切割點也可以從后往前找。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d",&n);

        vector<int> v;

        for(int i=0;i<n;i++) {
            int val,cnt;
            scanf("%d%d",&val,&cnt);
            for(int i=0;i<cnt;i++) {
                v.push_back(val);
            }
        }

        sort(v.begin(),v.end());

        int len = v.size();

        int Ans[10010];
        int sum[10010];

        memset(Ans,0,sizeof(Ans));
        memset(sum,0,sizeof(sum));

        for(int i=len-1;i>=0;i--) {
            sum[i] = sum[i+1] + v[i];
        }

        for(int i=len-1;i>=0;i--) {
            Ans[i] = Ans[i+1] + sum[i+1] + v[i];
        }

        int ans = 0;

        //for(int i=0;i<len;i++) {
        //    ans = max(ans,Ans[i]);
        //}


        for(int i=len-1;i>=0;i--) {
            if(ans<Ans[i])
                ans = Ans[i];
            else break;
        }

        printf("%d\n",ans);
    }

    return 0;
}

?