思路
dp去维护前缀f[i-1] - ai的最小值
CODE
1 #include <bits/stdc++.h> 2 #define dbg(x) cout << #x << "=" << x << endl 3 4 using namespace std; 5 typedef long long LL; 6 7 template<class T>inline void read(T &res) 8 { 9 char c;T flag=1; 10 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; 11 while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; 12 } 13 14 namespace _buff { 15 const size_t BUFF = 1 << 19; 16 char ibuf[BUFF], *ib = ibuf, *ie = ibuf; 17 char getc() { 18 if (ib == ie) { 19 ib = ibuf; 20 ie = ibuf + fread(ibuf, 1, BUFF, stdin); 21 } 22 return ib == ie ? -1 : *ib++; 23 } 24 } 25 26 int qread() { 27 using namespace _buff; 28 int ret = 0; 29 bool pos = true; 30 char c = getc(); 31 for (; (c < '0' || c > '9') && c != '-'; c = getc()) { 32 assert(~c); 33 } 34 if (c == '-') { 35 pos = false; 36 c = getc(); 37 } 38 for (; c >= '0' && c <= '9'; c = getc()) { 39 ret = (ret << 3) + (ret << 1) + (c ^ 48); 40 } 41 return pos ? ret : -ret; 42 } 43 44 const int kmaxn = 1007; 45 LL f[kmaxn]; 46 LL a[kmaxn]; 47 int n,k; 48 49 int main() 50 { 51 read(n); 52 read(k); 53 for(int i = 1; i <= n; ++i) { 54 read(a[i]); 55 } 56 57 sort(a+1, a+n+1); 58 LL temp = -a[1]; 59 for(int i = 1; i < k; ++i) { 60 f[i] = 1 << 30; 61 } 62 for(int i = k; i <= n; ++i) { 63 f[i] = temp + a[i]; 64 printf("f[%d]:%lld ",i,f[i]); 65 temp = min(temp, f[i-k+1] - a[i-k+2]); 66 dbg(temp); 67 printf("f[%d]:%lld ",i,f[i]); 68 } 69 printf("%lld ",f[n]); 70 return 0; 71 }