「vijos2728」最佳课题选择

2013年12月19日3,0970

描述

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

输入格式

第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。

以下m行每行有两个用空格隔开的正整数。其中，第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。

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

输出格式

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

样例输入

10 3 2 1 1 2 2 1

1
2
3
4

10 3
2 1
1 2
2 1

样例输出

19

1

19

代码

#include<iostream>
#include<cstring>
using namespace std;
int m,n;
long long a[21],b[21],c[21][201],f[201];
long long wk(int x,int y)
{
    long long s=1;
    for(int i=1;i<=y;i++)s*=x;
    return s;
}
int main()
{
    cin>>n>>m;
    memset(f,127,sizeof(f));
    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]*wk(j,b[i]);
    f[0]=0;
    for(int i=1;i<=m;i++)
        for(int v=n;v>=0;v--)
           for(int j=1;j<=v;j++)
              f[v]=min(f[v],f[v-j]+c[i][j]);
    cout<<f[n];
    return 0;
}

#include<iostream>

#include<cstring>

using namespace std;

int m,n;

long long a[21],b[21],c[21][201],f[201];

long long wk(int x,int y)

{

long long s=1;

for(int i=1;i<=y;i++)s*=x;

return s;

}

int main()

{

cin>>n>>m;

memset(f,127,sizeof(f));

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]*wk(j,b[i]);

f[0]=0;

for(int i=1;i<=m;i++)

for(int v=n;v>=0;v--)

for(int j=1;j<=v;j++)

f[v]=min(f[v],f[v-j]+c[i][j]);

cout<<f[n];

return 0;

}

« 「vijos1159」岳麓山上打水「vijos1240」朴素的网络游戏 »

hzwer.com _ Home | http://hzwer.com

「vijos2728」最佳课题选择

描述

输入格式

输出格式

样例输入

样例输出

代码

分类目录

热门文章

Myfriends

近期评论