自己模拟过程得出的思路

这个买债券的过程可以看成三个部分

1. 找到初始最大利息
2. 如果可以买入更加合适的债券就买入
3. 在最优组合的基础上利滚利,不断购入最优的证券

代码如下

#include<bits/stdc++.h>
using namespace std;
struct quan{
//	int id;
	int a;
	int b;
	double p;
}w[11];
bool ok;
int s,n,d;
int cmp(quan x,quan y){
	if( x.p == y.p ) return x.a < y.a;
	return x.p > y.p;
}
vector<int> f;
vector<int> zq;
void get_ms(int n){
	for(int i=1;i<=d;i++){
//		cout<<"???"<<endl;	
		while( n-w[i].a>=0 && f[n-w[i].a]==f[n]-w[i].b ){
			n-=w[i].a;
			zq.push_back( i );		
		}
	}
	return ;
}
int main(){
	
	cin>>s>>n>>d;
	f.resize( s+1 );
	for(int i=1;i<=d;i++){
		cin>>w[i].a>>w[i].b;
		w[i].p = 1.0 * w[i].b / w[i].a;//1利润需要多少钱 
	}
	sort( w+1,w+1+d,cmp );
	
	for(int i=1;i<=d;i++){
		for(int j=w[i].a;j<=s;j++)
			f[j] = max( f[j],f[j-w[i].a]+w[i].b );
	}//第一阶段实现 

//	cout<<"初始利息为 "<<f[s]<<endl;
	
	int lix = f[s];
	int sum=0;
	get_ms( s );	
	for(int i=0;i<zq.size();i++){
//		cout<<zq[i]<<' ';
		sum += zq[i];
		s -= w[zq[i]].a;		
	}	

	
//	cout << "利息是" << lix << endl;
	int k=0;//记录年数 
	
	while( sum!=zq.size() && k<n ){
//		cout << "sum == " << sum << endl;
		s += lix;
//		cout << "1.s == "<< s <<endl;
		ok=0;
		int lt=INT_MIN;
		int pos;
		for(int i=0;i<zq.size();i++){
			if( zq[i]>lt ){
				pos = i;
				lt=zq[i];
			}		
		}
		s += w[lt].a;
//		cout << "2.s == "<< s <<endl;
		lix -= w[lt].b;
		sum -= lt;
		for(int i=1;i<lt && !ok;i++){
			if( s >= w[i].a ){
				ok=1;
				zq.erase( zq.begin()+pos );
				lix += w[i].b;
				s -= w[i].a;
//				cout << "3.s == "<< s <<endl;				
				sum += i;
				zq.push_back( i );
			}			
		}
		if( !ok ){
//			cout<<"今年未能买下"<<endl;
			s -= w[lt].a;
			lix += w[lt].b;
			sum += lt;
		}	
		k++;
//		cout<<"目前利息为"<<lix<<endl;
	}
	for(int i=k+1; i<=n; i++){
		s += lix;
		if( s >= w[1].a ){
			s -= w[1].a;
			lix += w[1].b;
		}
	}
	for(int i=0;i<zq.size();i++)
		s += w[zq[i]].a;
	cout<<s;
	
	return 0;
}
//	for(int i=1;i<=d;i++){
//		printf("w[%d].a == %d\n",i,w[i].a);
//		printf("w[%d].b == %d\n",i,w[i].b);
//		printf("w[%d].p == %lf\n",i,w[i].p);
//	}
//	printf("\n");
//似乎有三个阶段
/*
1.(第一年)将买入的债券的年利息尽可能大
2.用所得利息逐步将债券换成性价比更高的债券,
  直到全部换成性价比最高的债券
3.性价比最高的债券不断利滚利 
*/