#P1336. 最佳课题选择

就不能直接不写吗

题意

要写n篇论文，可以从m个课题中选择。若写x篇第i个课题的论文，则需要A_i*x^b_i的时间，现要求求出最少时间

思路

首先我们想到的当然是DP。

那么问题来了。

怎么计算每篇论文的时间呢？

或许我们可以利用前缀和的方法来计算每篇论文的所需时间。

意思是，我们要计算第x篇论文单独所需的时间时，我们可以先计算前x篇论文的总时间，再计算前(x-1)篇论文的总时间，最后再把两者相减，就是这篇论文的单独时间

代码如下：

for(int i=1;i<=m;i++){
	cin>>a[i]>>b[i];
	long long old=0;
	for(int j=1;j<=n;j++){
		long long p=1;
		for(int k=1;k<=b[i];k++){
			p*=j; //幂
		}
		cost[i][j]=p*a[i]-old;
		old+=cost[i][j];//更新前面总和
	}
	cost[i][0]=0; 
}

然后再用正常的DP思路！

我们就可以得到！

#include<iostream>
#include<climits>
using namespace std;
long long n,m,a[210],b[210],cost[210][210],dp[210][210];//不开long long会爆
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
		long long old=0;
		for(int j=1;j<=n;j++){
			long long p=1;
			for(int k=1;k<=b[i];k++){
				p*=j;//幂
			}
			cost[i][j]=p*a[i]-old;
		    old+=cost[i][j];//更新前面总和
		}
		cost[i][0]=0;
	}
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=LLONG_MAX;//初始化DP数组
		}
	}
	dp[0][0]=0;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			if(dp[i-1][j]==LLONG_MAX)continue;
			for(int k=0;k<=n-j;k++){
				dp[i][j+k]=min(dp[i][j+k],dp[i-1][j]+cost[i][k]);//状态转移
			}
		}
	}
	cout<<dp[m][n];
	return 0;
}

一坨大大的

⑩。

这时我们会发现测试样例都不对，输出了2。

为什么呢？

不对劲，输出DP数组试试

0 2 2 2 2 2 2 2 2 2 2
0 1 2 2 2 2 2 2 2 2 2
0 1 2 2 2 2 2 2 2 2 2

这时我们发现了问题：新的时间直接覆盖了旧的时间，导致了实际的DP数组为cost数组。

解决方法也很简单，就是不计算每篇论文单独的消费，而是直接计算前面和这篇的总和

代码如下：

#include<iostream>
#include<climits>
using namespace std;
long long n,m,a[210],b[210],cost[210][210],dp[210][210];//不开long long会爆
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
		for(int j=1;j<=n;j++){
			long long p=1;
			for(int k=1;k<=b[i];k++){
				p*=j;//计算x的b[i]次方 
			}
			cost[i][j]=p*a[i];
		}
		cost[i][0]=0;//x为0时时间直接为0 
	}
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=LLONG_MAX;//初始化DP数组 
		}
	}
	dp[0][0]=0;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			if(dp[i-1][j]==LLONG_MAX)continue; 
			for(int k=0;k<=n-j;k++){
				dp[i][j+k]=min(dp[i][j+k],dp[i-1][j]+cost[i][k]);//正常DP 
			}
		}
	}
	cout<<dp[m][n];//输出结果 
	return 0;
}

时间复杂度为O(mn²)，可以AC。

别急着走，你以为这就完了？

注意到每篇论文的价值实际上是相同的，为1。

告诉我，你想到了什么？

没错，就是贪心。在价值相同时我们只需选取时间最少的即可。

这时，前面看似作废的单独每篇论文时间就派上了用场。

也就是说，我们只需计算出每篇论文的单独时间，再给它们排序，最后前n个相加即可。

这里还有一个问题，那就是该怎么保证选到第x篇论文时第y(y<x)篇论文已经被选到了呢？

这时我们注意到数据范围：a>=1,b>=1

在这两个数都大于等于1的情况下，可以保证ax^b>=ay^b，也就是单调序列。在这种情况下，贪心算法可以保证正确性。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,k,w[4010],sum,old,p;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		w[k++]=a;
		old=a;
		for(int j=2;j<=n;j++){
			long long p=j;
			for(int o=1;o<b;o++)p*=j;//计算幂 
			w[k]=a*p-old;//单独价值 
			old=a*p;
			k++;
		}
	}
	sort(w,w+k);//排序
	for(int i=0;i<n;i++)sum+=w[i];//计算结果
	cout<<sum<<endl;
	return 0;
}

时间复杂度为O(max(mnb,mnlog(mn))。

再写个快速幂。

#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,k,w[4010],sum,dream;
int pow_fast(int x,int y){
	long long p=1;
	while(y){
		if(y%2)p*=x;
		x*=x;
		y/=2;
	}
	return p;//快速幂 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		w[k++]=a;
		old=a;
		for(int j=2;j<=n;j++){
			w[k]=a*pow_fast(j,b)-old;//单独价值 
			old=a*pow_fast(j,b);
			k++;
		}
	}
	sort(w,w+k);//排序 
	for(int i=0;i<n;i++)sum+=w[i];//计算结果 
	cout<<sum<<endl;
	return 0;
}

时间复杂度为O(max(mnlog(b),mn log(mn))，比动态规划更优。

都给我点赞！

点踩被我发现你就完了。