/*1.sql 利用where，orderby好像就足够ac了---------2.N-水仙花数模拟过程就行-----------3.股票最大收益设dp[i][k]表示前i个股票交易k次的最大值dp[i][k]=max({dp[i][k],dp[j][k],dp[j][k-1]/history_[j]*history_[i]});//其中jres=max(res,dp[i][k]);枚举i,j,k即可*/#include using namespace std;int main(){double M;int N,K;cin>>M>>N>>K;vector history_;for(int i=1;idouble x;cin>>x;history_.push_back(x);}vector dp[N];double res=M;for(int i=0;ifor(int k=0;kif(k==0){dp[i].push_back(M);continue;}else{dp[i].push_back(0);}for(int j=0;jdp[i][k]=max({dp[i][k],dp[j][k],dp[j][k-1]/history_[j]*history_[i]});}res=max(res,dp[i][k]);}}coutreturn 0; }/*10000.0 4 21.0 2.0 1.0 3.0 1000.0 1 21.01000.0 2 21.0 2.0*/

1-闯关dp[i]=max(dp[i],dp[j-1]+val[i]); //满足条件 ch[j]=='b'&& kind[j] == kind[i]① 可以暴力枚举i,j，当然这样写是O(n*n)，需要优化②  定义一个vector<int> vec[kind]存下标pos，其中下标满足ch[pos]=='b'&&kind[pos]==kind，这样能卡过(1700ms通过)就没继续优化了。③ 继续优化可以发现对于一个kind，不需要遍历②的所有pos，而只需找到最大的dp[pos-1]即可，那么就可以继续优化到O(n)--------------2-最少施工队树形dp，转移方程dp[fa]+=(dp[son]==0? cost[{fa,son}]:dp[son])① dp[i]表示以i的子树所需的施工队,cost[{fa,son}]表示fa-son这条边是0还是1② 解释下方程，如果son子树已经需要派施工队去，那么fa-son这条边就不需要多的施工队了，否则看该边是0还是1--------------3-连续子数组最大乘积①可以发现0会把数组划分成一段一段，答案区间一定不会包含0②假如全部是正数，那么区间的乘积可以用2的幂次表示，所以记录2的幂次和即可(mp[8]=3，mp[4]=2)②对于一段不含0的区间，需要让负号为偶数，所有如果区间是奇数个负数，那么就删去左边第一个负数 或者 右边第一个负数。我的做法是用map<pair<int,int>,int> >mp存下所有的合法区间,mp[{l,r}]=sum，然后遍历mp求值。tips：输出-1的数据只有6%，通过94%或者96%可能是因为下面的数据--------------5         |    5    1 1 1 1 1   |   1 -1 1 1 14-最少操作①从后往前构造，如果a[n]这个数被置为0会怎么样。②a[n]不用置为0是数组什么情况实际上只有 2 3  1 4 4 4 5 5这样的才会说少用次数，不需要去消除4和5，而 2 4 3 1 4 4  5就不能保留4 。倒着去求就可以--------------代码是再牛客上直接写的，本地没有保存