Codeforces 467 C George and Job
做题感悟:这题其实不难,想的太多的,思路有点乱。
解题思路:
状态压缩方程: dp[ i ] [ j ] = max( dp[ i -1 ] [ j ] , dp [ i - m ] [ j-1 ] + sum[ i ] - sum[ i - m ] ) ; sum[ i ] 为前 i 项和 ,dp[ i ] [ j ] 代表选到第 i 个选择了 k 段的最大值,因为每一步都是最优的,so ~ 到达第 i 个的时候只要考虑,拿或者不拿就可以了。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<iomanip> #include<algorithm> using namespace std ; #define INT __int64 const double INF = 99999999 ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int mod = 3 ; const int MY = 100000 + 5 ; const int MX = 5000 + 3 ; int n ,m ,k ; INT sum[MX] ,dp[MX][MX] ; int main() { while(~scanf("%d%d%d" ,&n ,&m ,&k)) { sum[0] = 0 ; for(int i = 1 ;i <= n ; ++i) { cin>>sum[i] ; sum[i] += sum[i-1] ; } for(int i = m ;i <= n ; ++i) for(int j = 1 ;j <= k ; ++j) dp[i][j] = max(dp[i-1][j] ,dp[i-m][j-1] + sum[i]-sum[i-m]) ; cout<<dp[n][k]<<endl ; } return 0 ; }
做题感悟:这题很水很水,比赛时竟然两个人都没做出来,首先要仔细读题,然后确认题目无误后认真调试代码,还有就是想数据的时候别想当然的去想,每一组数据都要手推一下,谨记!!!!!
解题思路:
两者必定是先取两者公共的部分,然后自己一边的必定属于自己,注意两者在同一点的时候就可以了。