소감 ¶
2006-01-04 Accepted 1.123 500 |
{{| Dan-3a+2 ~ (k+9-a)*2 = (L(i) - L(i-1))^2 + min<sub>i+2<=k</sub>{ Da-1k } |}}
각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다.
위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서
{{| min<sub>i+2<=k</sub>{ Da-1k } |}}은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.
코드 ¶
~cpp // 10271 - Chopsticks #include <iostream> using namespace std; #define MAX_NUM 1000000000 #define MAX_STICK 5003 static int nPerson, nStick; // 손님수, 젓가락 수 static int stick[MAX_STICK+1]; // 젓가락 static int d[2][MAX_STICK+1]; // 다이나믹 테이블 inline int calcDegree(int i) { int x = stick[i] - stick[i-1]; return x * x; } inline int findMin(int k, int x, int n) { int min = d[k][x]; for (int i = x + 1; i <= n; i++) if (min > d[k][i]) min = d[k][i]; return min; } void input() { cin >> nPerson >> nStick; for (int i = 1; i <= nStick; i++) cin >> stick[i]; } void initTable() { for (int i = nStick - 1; i >= (nPerson + 8) * 2; i--) d[1][i] = calcDegree(i); d[1][nStick] = MAX_NUM; } void process() { int i, min; initTable(); for (int seti = 2; seti <= nPerson + 8; seti++) { i = nStick - 3 * seti + 2; min = findMin(!(seti&0x1), i+2, nStick - 3 * seti + 5); d[seti&0x1][i] = calcDegree(i) + min; for (i = i-1; i >= (nPerson + 9 - seti) * 2; i--) { if (min > d[!(seti&0x1)][i+2]) min = d[!(seti&0x1)][i+2]; d[seti&0x1][i] = calcDegree(i) + min; } } cout << findMin((nPerson + 8)&0x1, 2, nStick - 3 * nPerson - 22) << endl; } int main() { int nCase; cin >> nCase; for (int i = 0; i < nCase; i++) { input(); process(); } return 0; }