Nội dung Bài tập
- Mã:
- POSTERIZE
- Tên:
- Posterize (World Final 2017_F)
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 2 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- pvtran1995
intensity of the red, green, and blue colors. To compress an image or to create an artistic effect, many
photo-editing tools include a “posterize” operation which works as follows. Each color channel is examined separately; this problem focuses only on the red channel. Rather than allow all integers from 0 to 255 for the red channel, a posterized image allows at most k integers from this range. Each pixel’s original red intensity is replaced with the nearest of the allowed integers. The photo-editing tool selects a set of k integers that minimizes the sum of the squared errors introduced across all pixels in the original image. If there are n pixels that have original red values r1,.....,rn, and k allowed integers v1,.....,vk, the sum of squared errors is defined as
Your task is to compute the minimum achievable sum of squared errors, given parameter k and a description of the red intensities of an image’s pixels.
The first line of the input contains two integers d (1 ≤ d ≤ 256), the number of distinct red values that occur in the original image, and k (1 ≤ k ≤ d), the number of distinct red values allowed in the posterized image. The remaining d lines indicate the number of pixels of the image having various red values. Each such line contains two integers r (0 ≤ r ≤ 255) and p (1 ≤ p ≤ 226), where r is a red intensity value and p is the number of pixels having red intensity r. Those d lines are given in increasing order of red value.
Output
Display the sum of the squared errors for an optimally chosen set of k allowed integer values.
Sample1
Input Output
Sample2
Input Output
Sample3
Input Output
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...