http://poj.org/problem?id=3709?(題目鏈接)

題意

　　給出一個n個數的序列，要求將其中一些數改為另一個比它小的數，改動的花費為兩數的絕對值，完成改動后使得整個序列中出現過的數出現的次數大于等于K。求最小花費。

Solution

　　將原序列從大到小排序以后，我們可以發現，每次把連續的一段改成相同的數總是比離散的修改更優。于是我們寫出dp方程：${f[i]=Min(f[j]+s[i]-s[j]-a[i]*(i-j))}$。${f[i]}$表示將前${i}$個數修改，并且第${i}$個數保持不變的最小費用；${s[i]}$表示前綴和；${a[i]}$表示第${i}$個數的值。

　　考慮優化。斜率式：${-a[i]*j+f[i]=(f[j]-s[j])+s[i]-a[i]*i}$。

　　然而我們發現斜率${-a[i]}$并不是單調的，所以就不能夠直接取單調隊列隊首的元素了，那怎么辦呢？只好在隊列中二分了，二分的過程很好理解，詳情見代碼。

　　以上作廢，我在說什么鬼話→_→，${-a[i]}$顯然是單調的。。

　　再附張圖，這次的單調隊列里面的點構成的圖形有點鬼。。竟然是個類似于反比例函數的東西→_→

?

細節

　　記得開long long。。。

代碼

// poj3709 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 1ll<<60 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std;const int maxn=500010; LL a[maxn],f[maxn],s[maxn]; int n,K,q[maxn];bool cmp(int a,int b) {return a>b; } double slope(int x,int y) {return (double)((f[y]-s[y])-(f[x]-s[x]))/(double)(y-x); } int main() {int T;scanf("%d",&T);while (T--) {scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];for (int i=1;i<=n;i++) f[i]=inf;int l=1,r=1;q[1]=0;for (int i=K;i<=n;i++) {while (l<r && slope(q[l],q[l+1])<-a[i]) l++;f[i]=f[q[l]]+s[i]-s[q[l]]-a[i]*(i-q[l]);while (l<r && slope(q[r-1],q[r])>slope(q[r],i-K+1)) r--;q[++r]=i-K+1;}printf("%lld\n",f[n]);}return 0; }

代碼（強行二分）

// poj3709 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 1e18 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std;const int maxn=500010; LL f[maxn],s[maxn],a[maxn]; int q[maxn],n,K;double slope(int x,int y) {return (double)((f[y]-s[y])-(f[x]-s[x]))/(double)(y-x); } int find(int l,int r,LL x) {int res=l;while (l<=r) {int mid=(l+r)>>1;if (mid<r && x>slope(q[mid],q[mid+1])) l=mid+1,res=mid;else if (mid>l && x<slope(q[mid-1],q[mid])) r=mid-1,res=mid;else return mid;}return res; } bool cmp(LL a,LL b) {return a>b; } int main() {int T;scanf("%d",&T);while (T--) {scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];for (int i=1;i<=n;i++) f[i]=inf;int l=1,r=1;q[1]=0;for (int i=K;i<=n;i++) {int x=find(l,r,-a[i]);f[i]=f[q[x]]+s[i]-s[q[x]]-a[i]*(i-q[x]);while (l<r && slope(q[r-1],q[r])>slope(q[r],i-K+1)) r--;q[++r]=i-K+1;}printf("%lld\n",f[n]);}return 0; }

　　

轉載于:https://www.cnblogs.com/MashiroSky/p/6011890.html

總結

以上是生活随笔為你收集整理的【poj3709】 K-Anonymous Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。