受欢迎的免费网站建设,网站的优化怎么做,进出口采购网,长期大量手工活外发【BZOJ1831】[AHOI2008]逆序对#xff08;动态规划#xff09; 题面 BZOJ洛谷 题解 显然填入的数拎出来是不降的。 那么就可以直接大力\(dp\)。 设\(f[i][j]\)表示当前填到了\(i\)#xff0c;上一个填的数是\(j\)的最小逆序对数。 随便拿什么维护一下转移就好了。 #include动态规划 题面 BZOJ洛谷 题解 显然填入的数拎出来是不降的。 那么就可以直接大力\(dp\)。 设\(f[i][j]\)表示当前填到了\(i\)上一个填的数是\(j\)的最小逆序对数。 随便拿什么维护一下转移就好了。 #includeiostream
#includecstdio
using namespace std;
#define MAX 10010
inline int read()
{int x0;bool tfalse;char chgetchar();while((ch0||ch9)ch!-)chgetchar();if(ch-)ttrue,chgetchar();while(ch9ch0)xx*10ch-48,chgetchar();return t?-x:x;
}
int n,K,sum,a[MAX],ans1e9,f[MAX][101],s1[101],s2[101];
int main()
{nread();Kread();for(int i1;in;i)a[i]read();for(int i1;in;i)if(~a[i])s2[a[i]]1;for(int i1;iK;i)s2[i]s2[i-1];for(int i1;iK;i)s1[i]s2[i];for(int i1;in;i)if(~a[i]){sums1[a[i]-1];for(int ja[i];jK;j)s1[j]-1;}for(int i1;in;i)if(~a[i]){for(int j1;jK;j)f[i][j]f[i-1][j];for(int ja[i];jK;j)s2[j]-1,s1[j]1;}else{for(int j1;jK;j)f[i][j]f[i-1][j]s2[j-1]s1[K]-s1[j];for(int j1;jK;j)f[i][j1]min(f[i][j1],f[i-1][j]s2[j]s1[K]-s1[j1]);for(int j2;jK;j)f[i][j]min(f[i][j],f[i][j-1]);}for(int i1;iK;i)ansmin(ans,f[n][i]);printf(%d\n,anssum);return 0;
} 转载于:https://www.cnblogs.com/cjyyb/p/10486547.html
