广联达5.11 秋招提前批C++笔试分享

楼主我又来啦，今晚又看了看这道题，用动态规划做了，感觉应该没啥问题，不知道能不能ac #include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { int n; cin>>n; int k; cin>>k; vector<int> pos(n); for(int i=0;i<n>>pos[i]; } //先对pos排序 sort(pos.begin(),pos.end()); int l=0,r=0; vector<int> cover(n); //双指针法，求出cover[0..n-1] //cover[i]表示在pos中下标i之后(包括i)共有多少个馅饼与pos[i]的距离在k之内 //比如pos: 1 1 2 3 4 5 5 //如果k=1,则对应的cover: 3 2 2 2 3 while(l<n>> dp(n); for(int i=0;i<n>=0;i--) { for(int j=1;j<3;j++){ /*如果i+cover[i]==n并且必须恰好要有2次选择吃馅饼, 说明此时这个馅饼一定不能选择吃 否则的话，假如我们选择吃它，就会剩下一次必须选择吃馅饼的机会 但却没有馅饼可吃了,所以直接dp[i][j]=dp[i+1][j]*/ if(i+cover[i]==n&&j==2){ dp[i][j]=dp[i+1][j]; } /*如果i+cover[i]==n并且必须恰好要有1次选择吃馅饼, 说明pos[i]这个馅饼一定要选择吃，因为这样会吃完pos[i]以及之后 的所有馅饼，一定是最多数量，直接dp[i][j]=cover[i]即可 */ else if(i+cover[i]==n&&j==1){ dp[i][j]=cover[i]; } /*如果i+cover[i]</n></n></int></n></int></vector></algorithm></iostream>

纠正一下( 少敲了两个数字): //如果k=1,则对应的cover: 3 2 2 2 3 2 1

麻烦问一下行测等题可以修改嘛，比如说一些消耗时间长的先简单选一下，做完编程后再去研读

我的想法就是把所有馅饼的位置用一个数组记录下来，然后第一遍遍历计算吃掉最多的区间的馅饼，然后相应位置改成0。第二遍第一遍，然后两次相加就是吃的最多的馅饼。但是只过了30%