โจทย์: มีที่ดิน n แปลง สูงสุด h ชั้น กำไร = k² สำหรับบ้านสูง k มีข้อจำกัด m โซน: บ้านสูงสุดในช่วง li ถึง ri ต้อง ≤ xi หากกำไรสูงสุด
Input: n=3, h=3, T=[[1,1,1],[2,2,3],[3,3,2]] → Output: 14 (ความสูง [1,3,2] → 1²+3²+2²=14)
ขั้นตอนแก้
heights := array of n filled with h
for each restriction (l,r,x):
for i := l-1 to r-1:
heights[i] = min(heights[i], x)
ans := sum of heights[i]²
return ansตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int h, vector<vector<int>> T) {
int m = T.size();
vector<int> heights(n, h);
for (int i = 0; i < m; i++) {
int l = T[i][0], r = T[i][1], h = T[i][2];
for (int i = l-1; i < r; i++)
heights[i] = min(heights[i], h);
}
int ans = 0;
for (int i = 0; i < n; i++) ans += heights[i] * heights[i];
return ans;
}
int main() {
int n=3, h=3;
vector<vector<int>> T = {{1,1,1},{2,2,3},{3,3,2}};
cout << solve(n,h,T) << endl;
}Input
3, 3, {{1,1,1},{2,2,3},{3,3,2}}Output
14
