Hihocoder1044(상압 DP)

제목 링크
블로그를 보면 일률적으로 매우 간단하다고 말하고, 또 각종 소동을 일으킨다.체험이 나쁘다.
i번째 위치의 상황을 고려하면 우리는 앞의 m-1 위치의 상황만 알면 된다.그래서 앞의 m-1과 i의 m개 위치를 한 상태로 압축한 다음에 몇 개의 위치를 구할 수 있다. 만약에 q개를 초과하면 더 이상 고려하지 않는다.q보다 작은 상황을 고려하다.기본적인 상태 이동 방정식은 dp[i][j]=max(dp[i-3-1][j>>1], dp[i-3-1][j/2+(1> 1 ] , d p [ i − 1 ] [ j/2 + ( 1 << m − 1 ) ] ) ; 여기 j/2+(1#include #include #include #include using namespace std; int n,m,q; int num[1005],dp[1005][(1 << 10) + 5]; int main() { while(~scanf("%d %d %d",&n,&m,&q)) { for (int i = 1; i <= n; i++) { scanf("%d",&num[i]); } memset(dp,0,sizeof dp); int maxn = (1 << m); for (int i = 1; i <= n; i++) { for (int j = 0; j < 1 << (m); j++) { int temp = 0,x = j; while(x) { temp += x&1; x>>=1; } if(temp > q)continue; if(j&1)dp[i][j] = max(dp[i - 1][j>>1],dp[i - 1][j/2 + (1<1)]) + num[i]; else dp[i][j] = max(dp[i - 1][j / 2],dp[i - 1][j/2 + (1<1)]); } } int ans = 0; for (int i = 0; i < (1<if(dp[n][i] > ans) ans = dp[n][i]; } printf("%d
",ans); } }