洛谷 题解 P1336 【最佳课题选择】

详细解析解题过程

• 设计状态

dp[i][j]表示前i节课题写j篇论文花费的最少时间

• 初始数组

for(int i=0;i<=20;i++)

for(int j=0;j<=200;j++)dp[i][j]=INF;

//先初始化为INF

for(int i=0;i<=m;i++)dp[i][0]=0;

//写0篇论文的时间肯定为0吖

• 进行转移

for(int i=1;i<=m;i++)//前i节课程

	for(int j=1;j<=n;j++)//写了j篇论文

		for(int k=0;k<=j;k++)//第i节课程写了k篇

			dp[i][j]=min(dp[i][j],dp[i-1][j-k]+(ll)(a[i]*pow(k,b[i])));

• 取出答案

dp[m][n]

完整代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,m;

ll a[30],b[30];

ll dp[30][250];

inline int read()

{

    int tot=0;

    char c=getchar();

    while(c<'0'||c>'9')

        c=getchar();

    while(c>='0'&&c<='9')

    {

        tot=tot*10+c-'0';

        c=getchar();

    }

    return tot;

}

int main()

{

    n=read();m=read();

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

        a[i]=read(),b[i]=read();

    for(int i=0;i<=20;i++)

        for(int j=0;j<=200;j++)dp[i][j]=9999999999;//0x3f3f3f3f好像会太小

    for(int i=0;i<=m;i++)dp[i][0]=0;

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

    {

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

        {

            for(int k=0;k<=j;k++)

            {

                dp[i][j]=min(dp[i][j],dp[i-1][j-k]+(ll)(a[i]*pow(k,b[i])));

            }

        }

    }

    cout<<dp[m][n]<<endl;

    return 0;

}