分组背包（课题选择）

G. 4# 课题选择 [ Problem 4840  ] [ Discussion ]

---

Description

Matrix67 要在下个月交给老师 n 篇论文，论文的内容可以从 m个课题中选择。由于课题数有限，Matrix67 不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题 ii，若 Matrix67 计划一共写 x 篇论文，则完成该课题的论文总共需要花费 Ai∗X^Bi个单位时间（系数 Ai和指数 Bi 均为正整数）。给定与每一个课题相对应的 AiAi 和 BiBi 的值，请帮助 Matrix67 计算出如何选择论文的课题使得他可以花费最少的时间完成这 n 篇论文。

Input

第一行用空格隔开的正整数 n 和 m，分别代表需要完成的论文数和可供选择的课题数。以下 m 行每行有两个用空格隔开的正整数。其中，第 i 行的两个数分别代表与第 i 个课题相对应的时间系数 Ai 和指数 Bi。

Output

输出完成 n 篇论文所需要耗费的最少时间。

Samples

Input Copy

10 3
2 1
1 2
2 1

Output

19

Hint

【样例说明】
4 篇论文选择课题一，5 篇论文选择课题三，剩下一篇论文选择课题二，总耗时为2∗4^1+1∗1^2+2∗5^1=8+1+10=1。可以证明，不存在更优的方案使耗时小于 19。

【数据规模】

• 对于 30%的数据，n≤10, m≤5；
• 对于 100%的数据，n≤200，m≤20，Ai≤100，Bi≤5。

Source

石光中学 2018年 泉州复赛模拟 普及组 day1

 

 

 

状态设计

dp[i][j]表示前i个课题，分配j篇论文的最少时间

状态转移

dp[i][j] = min(dp[i][j], dp[i-1][k]+c[i][j-k])
其中c[i][j-k]意为第i个课题，写j-k篇论文的时间

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
int read(){
    int x=0; int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=1e3+100;
//c[i][j]表示a[i]这个课题被选择j次时对答案的贡献.
ll c[maxn][maxn];
ll a[maxn],b[maxn],dp[maxn];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*a;
        } 
        a=a*a;
        b/=2;
    }
    return ans;
} 
int n,m;
void ini(){
    cin>>n>>m;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            c[i][j]=a[i]*qpow(j,b[i]);
        }
    }
}
int main(){
    ini();
    dp[0]=0; 
    for(ll i=1;i<=m;i++){
        for(ll j=n;j>=0;j--){
            for(ll k=1;k<=j;k++){
                dp[j]=min(dp[j],dp[j-k]+c[i][k]);
            }
        }
    }
    cout<<dp[n]<<endl;
}