HDU1963Investment(DP)

时间:2023-12-16 23:59:44

简单DP,题解见代码

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABHcAAAAzCAIAAACSS3MlAAAY5UlEQVR4nO1dy27byNLu5/BjRHqI5B0M/Lb1BJNlgNn/vmibAMlD2DmxkEWQvYFsnBPnYgHJIgjgxSyyyYgUJZJn0WSz+spuihSLUn0ozMQUm2wWv67ur29kB4c3ZNzyPM/zvPdskGEwIgPZ/tjQ2Z6X6D0n2IzcQi4l/2A2ctfOG+s9B3iM6E4mjMhAtj82dLaTynJ7pvds7JKRS8k/5C4yfyOVVRnRnUwYkYFsf2zobCeV5fZM79nYJSOXkn/IXWT+RiqrMqI7mTAiA9n+2NDZTirL7Znes7FLRi4l/5C7yPxtQ5X1/X2u4/fT1vLHr88vaLjX+1dt+gIf3cEjPzw8qT//08uHTfwPvX1zcHjz9NboYX4XDbe/leSDNnxk2KapTAhI5UXU0JwYioCFnKp5nrbn5sf2LiJwOxFenB9+awXRy7839yeiCBnolm345MfbT+L4k7eRsXRjtg2ZBh8/7ApBLvr74UdPXg33T5+57d2auGswVpb62+/+qUCVvWGDFot1obJaLC01dXDTmGU2ZHTXnreeqW2S8ultnptbObY2REBBwm/IyLBlQ6KyrEXATk7JPE8j82N7F03wdiK8ODn81u0+DjdEETLQLV37JPrxAEMEcNRwWthhLn31uw0mkMraWWvirqEYf61VhK83ucomlXV4Y2qNwSOKj2CkKH+qYpDRlXodDE4r0rb2DnDRXYo7Tb0qwhY/cvtQ1mq/n4J+xJLT4i5yK8FWJaiREWTS63Y3B7AvE1lrGBcZtm2efLuB7aT3r2w//X6qtRK83ru5CJjIKTVleKNQP835IFV90GZIGYr5sV19ibxG/PH2k2hDv7+NwCuQ3rJFLLUT4cVdQp7a3nItyAD5X7E0IGQhiJCBbunOJ5AhUhn8cftbaWGbr9bIY4B1CkXlkv7qt52im7i0cJS4cpm3Srjay4gjtHo43KlbLMk9W2XtUq4ut4bYXptVW9XjrALMN3JczZP5HbhrIMad8/72t5lm6luwV9kWteZX0lvpJNrI+lVZMgyteWcd3HZfNS66l8TSni7Qq/wnY49aBcXDLamsmtsVrw+ixZHJnSLDtm2DUmz86SGCVPF97+YioJNT64B3h2zDgxiv0Ptb2J75sb1WZUne099ydxFe3CHkqV3jA9V9i8a9NIhaT11uCCJkoFu680nR9Hn56uGHeKGvfud5/v7tg1dwaOqxMp8qRZ/yJuArkcq3NRbgUoN4+PTyoeKzb27LPAfET7tusSf3bJW1Szl3bm2R2ZFVR9XToApooyJr3V3DMFkjVUQKVVlmQvqX9N6r8m5mDEpP62qfSQHUWsasdfATECg3tyzLsizr930AUxgmHtzbq4XHopd/y73CUuMVnCN7uL59U9+GcN5OTY5rdHh3Y5+P+aksqXu77Fjy/MnrvduKgIOcDg7XPQiCcNyX+bHdMZ1Mm39fEEC0XGGcsb2v5hFe5CbkqU2Po0Qz3qgSWQoNWQgiZKBbuvNJqbL+/v6+rKGevI2qRlhtcPD3mJl1Fooa+l/ac6l7iMyR283jpy2muZJ7tsrapZwztwZy1mXV4bqaeRmmG7VTkbXtrkGYtXy53oKpyi7fsh4oPEt639a+yvIYGbwBMdfgaO36W1JZ6/V6tVr1/kqgyXrde8agnFzrfdSjVTcqy307c99k/8O73HY29nmZn8qSu7TDfvJ+76YiYCQnjEWBKkuNY1ik/tbMj+16tFcm8ICXqBLAFqvRqqyKqOqkNW/qYoiQgW7pzifVcz29BV3XDw9PoJccV/P3mJl1GkVFBvjVvNtkAS51qyxHbjePnzbd4kru2Sprl3LO3BpoqbdbTP4xuq5eZWk3aq8ia9NdQzAYuuUwHqqyfN6yu6T3bC3OGCwIqs2P9NEDDVVWuzMGl8tlHMe9vxKDSV13Laksg9ztUmXptyOVhcnk141IZRUmzx6UcistqeIIVVn6RbDwcDvmx3ZHq6srldXXjMEDMOm/qtE6VVndRMhAt3Tnk+q5iiGsw3JQq7HKsnnMu+315G0kJjH6z/UKcKl7xiBSlVXbKmuXcs7cWmN7o1qpfl6GdiNSWQ2tdkqnv8ryecv7orL0dRTSGtlNh271Orjt3S8Wi0UURb2/Em6FuwybqtV61T5jEJXKwj1Na0djn9U4kQxD8w6+tTNjsCZLxn0F4b8NOXepLGPBkWwPdybM89xjsnSIymplxmBfu1+I/Bd7LZTZDg1ZCCJkoFu684n6XO9vfxses3YXBB+PueYRyQys2tYBbbIQl6pdz9LuF+3MGPTkXt3xypOIVJY9tjeax26vAqw3aqMia99d+M2gWpV3Z66Iwyb5+5f0Xq3l3S/KIGJfirqpylLR4n4JURThUVm1PfR2r5p+aqqyQCpLDhu3IVwP0r/x7PSeje2ZxjdRsprwLXDRsPm9+xSB2++mPkUzh633td9oTyzP8/V6XXdaiMpyrU62KavmEV6cHPLU5tupvaFylLNT1zAQhyFCBrqlO5/oFU0uNWRrr9bYY1IPutL2KsNUiFfDXOrcyb2t3S/8RoGKotSoVWaidzuUc+bWGtu992TyrHpqbhR4tQ5L6DBMUq3AV7CT1Og3ucquH/WS4CrpfVrrewwqK8+qqC3vRtqOymq3v3m1WqVp2vsrqUwKPZA0dV617uQeoLKqu7u7NjdoQxwoRQWNxDrY0dhXY7CmkaS1jW83sBL68fZB/gm2pdQC7vvebUVAJqe42o+3n6SZaSqH7Q9iLWt7Yev1erlc1p0WprIOrDvtBqisrX+VOH//yjyIau50MEY/YQgiZKBbuvOJSQvxq2ljAuareXvMvb+zQlEpJ524VPWq0mvgs5O7Flo9WGFXWfbk+FSWNba7G5COqsdaBVgrkVYqsnbdhd2k0SpucgDxqIgfHp7UyYSgkt6jbaiydsqQ7TFI1qftYuzrz5puV0W2HUuSBOmSVD8TdW3vOcFm5Ba3NdhAi1w6JP+0W/V0UJHhchdZB0YqqzJSWWTCKPZtZoZOcTwfQyNTLI5jUlk7aeQWp21hc/y9s779027V03lF1re7yDo3UlmVkcoiE0axb1NTZrqj+XgFmW5RFJHK2kkjt9hMTDcKXXdALsXun3arno4rsv7dRdaxkcqqjOhOJozIQLY/FkWRx7osvEYqy+2Z3rOxS0YuJf+Qu8j8jVRWZUR3MmFEBrL9sTiOkyTpPRuNjVSW2zO9Z2OXjFxK/iF3kfkbqazKiO5kwogMZPtjy+XSYyd3vEYqy+2Z3rOxS0YuJf+Qu8j8jVRWZUR3MmFEBrL9sSRJcH3EItBIZbk903s2dsnIpeQfcheZv5HKqozoTiaMyEC2P7ZarQa98Q+pLLdnes/GLhm5lPxD7iLzN1JZlRHdyYQRGcj2x5IkIZW1k0ZuIZeSfzAbuWvnjeWDRZZlaZquVqvlchnHcVSC/5uvNMiyjJ+cpulyuVwsFovFgv+apqn4Vb+ycpf1er1cLvn1l8sl7/rdxkMS0IN4SMAA4iEBA4iHBAwgHhIwIMuyoaqsLMtWq1WSJLzMLAD4n1EUJUki6K6XIljG+Jey4MXhv9frdZIkoogmSQLTEvYZxEMCBhAPCRhAPCRgAPGQgAGch0NVWavVChYbiDiO+cE4juM4Xq1WeVmKxDlKf4O7FK1WqziO//z5w6+pJNziQxPQgXhIwADiIQEDiIcEDCAeEjCA8xCLyjLSUSF3XnJaGQLmRWK9Xq/Xa854WKiSJOFpxU+O7grljmma8u4QXlz5jdI0dWebMFwQDwkYQDwkYADxkIABxEMCBjTjIRaV5QB/Bj75lWdd9EmI8sMn0Wby6C0vMHEccxfwubOijPHktoIk5trC83kRopKznyAeEjCAeEjAAOIhAQOIhwQMcPAQl8rSRWEOZr7yEV5YfkThUQqAOI13S/DeBd7xAMeFeY8Fn0fLkaYpdxPsouBzbakI7Q+IhwQMIB4SMIB4SMAA4iEBA0J5iFplCWmoc9q9vjAuwYsKPzkDPRnKnF1x/nK5FP0T4gRazrhvIB4SMIB4SMAA4iEBA4iHBAwI5SEulQWRlbvEiN4FnnU+BKw8JEwo+ipEb0QGxnz1ZZGivC0ARFrqothzEA8JGEA8JGAA8ZCAAcRDAgb48BCFyjJKQ2Wdoq2LQkkr1iOKVHwPGXg+3OIzKhc7RuWHFBbl2kcqP/sG4iEBA4iHBAwgHhIwgHhIwIDGPESqsuB+L4LW7i4K/sxiaaNIxSfdwlsI74g5lHBEmE+xNQ4BU4nabRAPCRhAPCRgAPGQgAHEw93DweFN7b/5n7W2tTw35iEKlQWRZdkafEhb5D5JEmWLTOVJ+LTI5XIJ+x7EtwuyEjAJn0wJwVc3KmcS9hDEw13AbJKzSd+Z2AjEQwIGEA8JGEA83A34qyz9347zt4YgHjZQWbMJE5jMjMfhYfP58+mYMe14lt2fj+Dxo8timuPd2Ug6vST6/AJe5+hKlJ8+vl0gP5TkBPDTeDpX0s0m8kGzc2ruKF3B9o5MUO8eklxJC9NZn9b+gL7JbTn391sNMrBdDJ9lG5XTbW3RXHSA6bvB7sc3NGY5Yx1Lmnk+ZrmLEBoGrrKGwcMP9wfPfn6XDv3zl+hrfP6PfPafF8+Un8CRw5uDw/t37WSrdYDwUoQWW8DngUyvHEW0UiKVM8ohQDs8vDxijB2/5jz8Zq8rS8wmSt0AzppNBuC2cGhF6d1zpef+44tfeV2R0YsYBCibhzcHhzePr/50+1DtwcnD1ydy02FyTfUyXnB1VDtChVNlhcbDUJU1m4DgBsIgPD6fjkVEtJ9fHs2yTJyUZdfHo/PPyyUfn319zNij009RFEWXx6Ozr8VIXHWZLLs+GZ1/KSbRXh4xxo6ubDN0u0f1UI4qQqouhK5QNBL4U/Kgej/jZW0+N6Y33d0nuTmtfo7xZ78HrHny5n4zItPGgpclD5fyV+GNk79FqRNxvD8e9oHZJGcsZyxvLG3rsRcqa0g8/HBfVIpS0/Cfv6qm258Xz0BT79fPx4ZW3T9/geTvnt9omg0B5tOxIZzYAn4RnlTZVVxAjamzyQYdQp2hZR7enfJu0pM3ZSVuqSsLlDrUVoVidNkmMBel/N1zi1KyFRlzEZPTHt789QHelys3pPDi4eURY2x0/rU6eT4dj6f3VC9jxeDGsjaJh4Eqaz4dw7qm/FM5XP1tOV99gOsqhPJSwZckrt+cMHZ0uVhAmZhlGb/MfZbBbTejKLo7HbFKjPWM6lnrnGDxSgmlF8+WLNDn1ruHJK/9UdGT5prR/ID1yRv6zQ44E0Di4Xodyxt0wmWvmcbDfYzjE5ZPZsV/K8zzMSvUF+M/6Udm1Z/Fy5zljOUzcHymXarQTnpa25lDwrB4+P3qI2waKn/mv34+hh3whiajjA/3+Iaz5FjkOKkIR7MJG0+nEygLJpOy1ye0+6c/tMfDq2PGTt68sUVkLZLz2G3sRfR6FwOFWnasKktGVWR8ipissn79fAz/RIk6Hl4eMTY6vXPz8NPpI36OMR7Op+NhlMnhw7akyqiX0K7LCoqHTcaypEErU8MexETz+fo1xWHeDZamKT8+OvsSa1+auz5hbHT+Wf7Id5Ik/zlmbHxxj6NpWz2V2txX/3aqBXudbL2sj88ddw9I7vrVNMXDNihmIUVN8oZ+8wPgYRGvdR6m5QfgFR7u3+5Ds0ILSWNH83wMRNd8mk+m2pEJGP4qL6JMPpxNcjbO5+UFwWilKa180wGOZSnAz8MalSVadZXccgCOg6FBbQzN81yKOHwqczmhmbfgZlBlDU8mbMDDL+cjNr74lsHOVBlysBbuNqis4UjUJmikskCR8S5iQlbpd0QOAw+vjhh7dHpXw8MvZ6PR+VdbPCSVtWUYJZZbMvW1BMuIoHjYYF2WaS2Q0sEk/amez2fKpmmafrsYMcbY6OyLtG1Lds8XW42n8xwO+BZR+8vZiLHR2Wc4FXK9XqffLkyTOnoCnGHSTGUVbrM/kOuyzmVg+n3Uc3yT25sfHg0T1wN6tWsa+q1ExcNyQyFl+yC960LiYZKIjyRIPNwvfZXnORQzs2pYSVc4xiPjafXnBIxuVcwW4kpWWca0yi2GoLKGzkPT4JWps/zD/cHhx8dgPYnUg/7r5+Nq2QkyzCaMjcdgHZFBKkhTCgt9xf9XNOBkEeZckNQPOuLh9Qljk+s8z62zC+TZmMrUd6iyxuPdHcbK89ymsmzrr/Qi4y5iBdR1WdgGskJ5+OVsxBfwu3n47WI8vri33ZRU1pbhOWOw9nh3aDEehqoseR4cU6KjaJqLcFidX0in0fnX8hte5Ye0705HjI1OP5e7asJ7sfHF19UKdEvcnY0YG/HFWnBKzL1x4nxPsNYbxr/r592B+fyV9rFe1vKOlOTWu9tfsTFz1iVVntWhacWDX3Jfv8nIyr2DVioPq91aZR4WqVYSD2NlNe3eTRGEgBMFJ6wQP9OxpIJsRxiTzKCyxPVllWVMq9wCscraGR4ausPFIpPDm4NnH6HKUlqEmqb68+IZvnVZygCKYTxFiTZgFIuNx2PLRMEqIPdZb3XKw/uLsewWPaxLrpNDurYWi0vd3dVZ7pGld8+Ne8OAIuNVxJDOGGzMw6/nI8aOL808vDpmJujdHYZfCR1CWWQFp//pgmqb0wW7iIeBKkuJk7Y50vKY/3WZbz4MdXRVfcOLZyj6dPqIPTr9FKntg/l0zMYX34ovfy0W/z19VEisuPy4cpqmqCVWvqHKsv9su6znO7JdPiS5JWt+M2ysp/smD/Ib73goeJgksAxUPCxhbKemqeDhQpwv83AvJRZcHFXYOJ97qyzliLigj8rS06JXWbvHw5pJR2IWk7rg6s+LZ6bJgV6znraLmoCtd+iIzU9B9HRu8rN95bAdHpqbscqkF0XAms8v34G192wX4FuUbMe9ipissjyXfnWGFnh4fcLY6PSuJh66R6toLGvLcE8RhBrMcWaLKqvTeLiZyrIMOlR7Bl5PGDv5TykK+V4wR5eLSMHlEdNUVpZl/EIX93xn+s+nj/j82zgqPyeXZRmyuGvKTAu7X5h+tl3W7x1Z7x6S3Jzz0G0nDF3FXsn9/ZaB7wzCTxyoPCwPqjws/6HM9pZ5uK9QZu4JLeQ5Y9CggkwzBsWaKzhjUE+rZAaZytpJHtZ3wPNf1TaiZQkWwk3PTCESjr5oUUiorHw+HZt2flWvvmWV1RMPTR14rorbvIcun2GxkwNaDVWWKDJeRUxRWX570nSDlnh4fVIuIXHwkFQWKig6ymeEyme3jGboOh422GNQWf2jhjsRO7MsW389HzE+aTZaLBb//f9HfKv15etjdvy6lIx3p6NiB/b1m5NyDre4/HXOd3hnxeewYO5FR2BWoqGb24FzhwfLhz9yYyVuWeLmdVmPd+S6e0hy25ouy24WYL699QE9kttOtVyWs3+1WolyIjob4PTZGMC4N3FejguLXgrAw+o0BDzcLtR9BcWkQXkjinym7n6Rz4rdL+B+GNO5qrKm41IpaResScs3G8SisnaVh46m4ferj1AywS2nv199LPrdP9yDRl6fbT4HNF1VjU+ZouNM/wRhdQll4/atD2X1x8PQ3dit1aa0QdMOwbDEsfpTnhloKTLmIiZB38m9nxmDbfLwesIYG53eVTz8fDYeX8zBafe0LgsT3PMDHalqzwnFFuJha18lVlb0ZtWXCq7+rzr/+HWxMvtamhowuS47HuQpA5NZ8TCmmQTHr5P0+kQ/3lsvlymTNdtRKElAt6ff89i2qTC/o5oMG19m7be2DM9pE5pyFWu6g1/yAL8BHsb//vsvLz+88IjpBBBKB5jeY5GmKfw8Qqx9h26/MJ8avpGl7AoobbauH5mpUw3VKYgT9XbGndyLtPCccT7FMpa1mzyE668O5aae5RPDpp/k5fj4JBaHYcsKa8B3qiw12VZbd73yUNnYwug6y/nGcbBdElrmomQrGq4i4yh9hrQ9jRt3wMNreQnW6OzLHtfLiKGMVgWpLD35hthOPGygsryyLiYpwptxCejOZW3uxUAen/K4X+MGhBAQD4cJbV3WwEE8JGAA8ZCAAcRDgoDnjMEutrvYGg87UVlpmsIJjv47Cwu9KEQk/EnMeoQjesrgHRUqggDxcJjYNZVFPCRgAPGQgAHEQ4KAYyyr608Pb42H7ausTJ6bGLQsW2yhyKEM+PIrK1MnldOoFBE4iIeDxU6pLOIhAQOIhwQMIB4SMGCbPGxZZXGFx6c5xuVXkBW1F5oWnrBer7lf+APopYhAyImHBBwgHhIwgHhIwADiIQEDtszDAJVlzIRyEE5z9F+QLS7CJzUKCagnF49HU2/3FsRDAgYQDwkYQDwkYADxkIABCHnYwliWkntxe05xR171K2RZliSJmNFo/Moy1JH88agUEXLiIQEHiIcEDCAeEjCAeEjAgB552PKMwTRNY/DxYz33NqEp/q3PldRvIeZEKl8Ho+JE4CAeEjCAeEjAAOIhAQOIhwQM2DIP/wdNp8FqbaiRBwAAAABJRU5ErkJggg==" alt="" width="697" height="31" />

 #include <stdio.h>
#include <string.h>
#include <algorithm>
#define mem0(a) memset(a,0,sizeof(a))
#define MAX(a, b) (a > b ? a : b)
using namespace std; struct BondsV_I
{
int Value;
int Interest;
}Bonds[];
int Amount, Year, BondsNum;
int dp[];//由于题目说利率不会超过10%,所以也就是不会超过1000*1.1^40,小于50000 int main()
{
int Case;
while(~scanf("%d", &Case))while(Case--)
{
mem0(Bonds);
scanf("%d%d", &Amount, &Year);
scanf("%d", &BondsNum);
for(int i=;i<=BondsNum;i++)
{
scanf("%d %d", &Bonds[i].Value, &Bonds[i].Interest);
Bonds[i].Value/=;//题目说Value都是1000的倍数,所以直接/1000减小复杂度
}
int ans = Amount;
for(int year = ; year <= Year; year ++)//由于存钱的利息一次性投两年和分开投结果没区别,
//甚至一年后可能还会有更好的方式,所以下一年可以只有上一年得到
{
mem0(dp);//dp保存的是这一年所获得的的利息
for(int i=;i<=BondsNum;i++)//对于每一种方式
{
for(int j=Bonds[i].Value;j<=ans/;j++)//由于可以选择任意多个,所以是完全背包
{ //Value/1000,所以相应的钱/1000
dp[j] = MAX(dp[j-Bonds[i].Value] + Bonds[i].Interest, dp[j]);
}
}
ans += dp[ans/];//更新这一年获得的数目
}
printf("%d\n", ans);
}
return ;
}