《算法竞赛进阶指南》0x51线性DP Cookies

2021-04-07 07:27

阅读：554

标签：while main 根据 ble pair cookie 通过 pac blank

题目链接：https://www.acwing.com/problem/content/279/

题目给定一个长度为n的序列g，和一个数m，要求将m分成n份，设定为数列a，使得数列g与数列a的乘积最小。根据排序不不等式，在g是升序的情况下，a是降序才会使得结果最小。所以对g进行降序排序之后，题意中的相对大小a[i]应该是升序的，所以此时每人分得的应该是降序的。

给第i个定数量的时候要知道前面有多少个一样的，阶段是分配完第i个人的量，前i个人一共用了j，若是每个人的数量都>1的则可以等价的转移到另一个[i,j-i]的等价集合，如果是1，则向前搜索长度连续的都是1的最小的目标值。最终通过回溯查看转移的方式，对结果进行保存。

代码：

#include
#include
#include
#includeusing namespace std;
typedef pairint,int> PII;
const int maxn = 32;
const int maxm = 5050;
int n,m;
PII g[maxn];
int s[maxn];
int ans[maxn];
int f[maxn][maxm];
int main(){
    cin>>n>>m;
    for(int i=1;i){
        cin>>g[i].first;
        g[i].second=i;
    }
    
    sort(g+1,g+n+1);
    reverse(g+1,g+n+1); 
    memset(f,0x3f,sizeof(f));
    
    for(int i=1;i1]+g[i].first;
    
    f[0][0]=0;
    for(int i=1;i)
        for(int j=1;j){
            if(i>j)continue;
            f[i][j]=f[i][j-i];
            for(int k=1;k//枚举有多少个连续1 
                f[i][j]=min(f[i][j],f[i-k][j-k]+(s[i]-s[i-k])*(i-k));
            }
        }
    
    coutendl;
    
    int i=n,j=m,h=0;
    while(i){
        if(f[i][j]==f[i][j-i])j-=i,h++;
        else{
            for(int k=1;k//枚举有多少个连续1
                if(f[i-k][j-k]+(s[i]-s[i-k])*(i-k) == f[i][j]){
                    for(int u=i-k+1;u1; 
                    i-=k,j-=k;
                    break;
                } 
        }
    }
    for(int i=1;i" ";
    coutendl;
    return 0;
}

《算法竞赛进阶指南》0x51线性DP Cookies

标签：while main 根据 ble pair cookie 通过 pac blank

原文地址：https://www.cnblogs.com/randy-lo/p/13390342.html

上一篇：Leetcode.283 | Move Zeroes(Python)

下一篇：输入10个整数，按照从小到大进行排序(选择排序)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《算法竞赛进阶指南》0x51线性DP Cookies
文章链接：http://soscw.com/index.php/essay/72302.html

亲，登录后才可以留言！

《算法竞赛进阶指南》0x51线性DP Cookies

评论

热门文章

推荐文章

最新文章

置顶文章