题目链接
洛谷 P1853 投资的最大效益
Task 1：100pts+ #11 TLE
对于长期持有一份债券，考虑转移较为麻烦，考虑按每年分别考虑，那么持有 \(x\) 债券 \(y\) 年，本金 \(a_x\) 元，可得 \(a_x+b_x\times y\) 元，赚了 \(b_x\times y\) 元；而 \(y\) 年分开考虑，每年本金 \(a_x\) 元，可得 \(a_x+b_x\) 元，赚 \(b_x\) 元，\(y\) 年即为 \(b_x\times y\) 元，二者相等。
所以可以看为每年单独考虑，分别进行决策，每年利益最大化后，总利益便也最大化了，时间复杂度 \(O(ndS)\)，其中 \(S\) 可达 \(1.1^{40}s\)，会超时。
#include<bits/stdc++.h>
using namespace std;const int D=15,S=30000000;
int s,n,d;
int a[D],b[D],dp[S];int main(){scanf("%d%d%d",&s,&n,&d);for (int i=1;i<=d;++i) scanf("%d%d",a+i,b+i);for (int i=1;i<=n;++i){memset(dp,0,sizeof dp);for (int j=1;j<=d;++j){for (int k=a[j];k<=s;++k) dp[k]=max(dp[k],dp[k-a[j]]+b[j]);}s+=dp[s];}printf("%d",s);return 0;
}
Task 2：时空一次优化
注意到题目中一个奇怪的条件：\(a\) 是 \(1000\) 的倍数，所以对于总金额除以 \(1000\) 余下的零头，不会影响决策。考虑缩小上一份代码内层 \(k\) 的循环范围，对于 \(a_i,s\) 都主动整除 \(1000\)，这样整体时间复杂度就少了 \(10^3\) 这一量级，还不会出错。
#include<bits/stdc++.h>
using namespace std;const int D=15,S=46000; // s_max=10^6,S=(10^6*1.1^40)/10^3
int s,n,d;
int a[D],b[D],dp[S];int main(){scanf("%d%d%d",&s,&n,&d);for (int i=1;i<=d;++i) scanf("%d%d",a+i,b+i);for (int i=1;i<=n;++i){memset(dp,0,sizeof dp);for (int j=1;j<=d;++j){for (int k=a[j]/1000;k<=s/1000;++k) dp[k]=max(dp[k],dp[k-a[j]/1000]+b[j]);}s+=dp[s/1000];}printf("%d",s);return 0;
}
Task 3：时间二次优化
再次进行时间上的优化。注意到每次都需要求一遍 \(\big\lfloor \dfrac{a_j}{1000}\big\rfloor\) 至上一次的 \(s\) 这一段，可以优化掉，每次在上一次基础上继续往后计算即可。时间复杂度直接降到 \(O(dS\div 1000)\)，其中 \(S\) 为最终答案。
#include<bits/stdc++.h>
using namespace std;const int D=15,S=46000;
int s,n,d;
int a[D],b[D],dp[S];int main(){scanf("%d%d%d",&s,&n,&d);for (int i=1;i<=d;++i) scanf("%d%d",a+i,b+i);int m=-1;for (int i=1;i<=n;++i){for (int j=1;j<=d;++j){for (int k=(m==-1?a[j]:m)/1000;k<=s/1000;++k)dp[k]=max(dp[k],dp[k-a[j]/1000]+b[j]);}m=s,s+=dp[s/1000];}printf("%d",s);return 0;
}