官方解题报告：
1001 hdu 4370
题意：
给你一个n*n的矩阵，求另一个矩阵满足如下条件：
1.X12+X13+...X1n=1
2.X1n+X2n+...Xn-1n=13.for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n).使得∑Cij*Xij(1<=i,j<=n) 最小，官方解题报告已经很完善这里不再罗嗦，只是强调一下在自己出现的错误：
1：这里分别得到由1,n出发的环视如果不存在返回的都是inf如果令inf = 0x7fffffff或者0x7f7f7f7f时，相加会查数据范围，这里要给出最大值为2^29
2：这里由1，n出发得到的环必须至少经过一个点，因为条件1，2应经限制了。
View Code #include#include #include #include #include #include #include #include #include
1005hdu 4374
题意：
有一个n曾的楼，从第一层往上走，每一层都有m块，可以从对应的本层的第y块跳到上一层的第y块，要求限制每一层只能往左右走，而且走的最大长度为T，问到达第n才层后的最大得分（ps:这里每一块都对应着一个得分，给出n*m举证表示得分）；
思路：
这里简单的dp O(n*m*m)肯定会超时，所以这里要用单调队列来优化，这道题目和上次比赛的1003一样都是用单调队列来优化的。
View Code #include#include #include #include #include #include #include #include #include #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define N 107#define M 10007#define inf 0x7f7f7f7fusing namespace std;int dp[N][M],sum[N][M],map[N][M];int q[M*2];int n,m,X,T;int main(){ //freopen("din.txt","r",stdin); int i,j; while (~scanf("%d%d%d%d",&n,&m,&X,&T)) { CL(sum,0); for (i = 1; i <= n; ++i) { for (j = 1; j <= m; ++j) { scanf("%d",&map[i][j]); sum[i][j] = sum[i][j - 1] + map[i][j]; dp[i][j] = -inf; } } dp[1][X] = map[1][X]; for (j = X + 1; j <= m && j - X <= T; ++j) dp[1][j] = dp[1][j - 1] + map[1][j]; for (j = X - 1; j >= 1 && X - j <= T; --j) dp[1][j] = dp[1][j + 1] + map[1][j]; int front,tail; for (i = 2; i <= n; ++i) { front = 0,tail = -1; //左扫 for (j = 1; j <= m; ++j) { while (tail >= front && j - q[front] > T) front++;//保持对头满足小于T if(dp[i - 1][j] != -inf)//因为得分由负值，所以要限制一下 { int tmp = dp[i - 1][j] + map[i][j]; while (tail >= front && tmp > dp[i - 1][q[tail]] + sum[i][j] - sum[i][q[tail] - 1]) tail--; q[++tail] = j; } if (tail >= front) dp[i][j] = max(dp[i][j],dp[i - 1][q[front]] + sum[i][j] - sum[i][q[front] - 1]); } //右扫 front = 0,tail = -1; for (j = m; j >= 1; --j) { while (tail >= front && q[front] - j > T) front++; if(dp[i - 1][j] != -inf) { int tmp = dp[i - 1][j] + map[i][j]; while (tail >= front && tmp > dp[i - 1][q[tail]] + sum[i][q[tail]] - sum[i][j - 1]) tail--; q[++tail] = j; } if (tail >= front) dp[i][j] = max(dp[i][j],dp[i - 1][q[front]] + sum[i][q[front]] - sum[i][j - 1]); } } int MAX = -inf; for (i = 1; i <= m; ++i) { MAX = max(MAX,dp[n][i]); } printf("%d\n",MAX); } return 0;}
1008 hdu 4377
题意：
定义：U(A) 为序列A的最长上升子序列，D(A)为序列A的最长下降子序列，H(A) = max{U(A), D(A)} 求1-n的全排列里面所有序列的的H(A)的最小值。
思路：参考官方解题报告
举例10 -- 16 他们的sqrt（）都为4 而10到12 都是分出三段，13到16 都是分出四段，我们按长度为4= sqrt(n)来分的，他的最长下降子序列已经确定为4，而最长上升子序列不能超过m所以对于分出三段的来说只要他的最前边的一段取出1个或者2个即可，又因为我们呢要保证字典序最小，所以我们把1放在最前边剩余逆序即可，而对于分出四段的我们必须从前边取出一个故必须降序。
View Code #include#include #include #include #include #include #include #include #include
1010 hdu 4379
题意：
序列{X1, X2, ... , Xn}由 Xk = (A * k + B) % mod产生，在序列{X1, X2, ... , Xn}中选一个子序列 {Y1, Y2, ... , Ym}是盖子序列满足：
Yi + Yj <= L (1 ≤ i < j ≤ m), and every Yi <= L (1 ≤ i ≤ m ) 求最长的m
这道题目最坑爹了，卡数据类型，思路参考官方解题报告：
View Code #include#include #include #include #include #include #include #include #include