一小学贪心

HDU 3552 I can do it!

题目大意：一个元素分为2个属性，a和b。然后将元素分成2个集合A和B。求出"A集合的a属性的最大值+B集合的b属性的最大值"的最小值
解题思路：一篇很详细的结题报告http://blog.csdn.net/dgq8211/article/details/7748078

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=111111;
const int INF=0x3f3f3f3f;
struct Node{
    int x,y;
    bool operator<(const Node& rhs) const {
        return x>rhs.x;
    }
}a[maxn];
int n;
int main()
{
    int T;
    int cas=0;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+n+1);
        int ans=INF;
        int b=0;
        a[n+1].x=0;
        for (int i=1;i<=n+1;i++){
            b=max(b,a[i-1].y);
            ans=min(ans,a[i].x+b);
        }
        printf("Case %d: %d
",++cas,ans);
    }
    return 0;
}

------------------

二 DP计数

HDU 3545 Board Coloring

题目大意
给定一个4*n的矩阵a[i,j]。(1<=i<=4 1<=j<=n)你要在里面填0~255的数字。
然后使得填了以后满足以下约束：
1：a[i,j]>=a[i,j-1]
2：对于一些给定了限制(i,j,i',j')，必须满足a[i,j]=a[i',j']。
解题思路
状态转移方程还是很好想的f[k,i1,i2,i3,i4]=∑f[k-1,j1,j2,j3,j4](i1<=j1,i2<=j2,i3<=j3,i4<=j4].
对于题目中相等的限制，可以表述为（p[x1]<y1）xor (p[x2]<y2）把f[p[1],p[2],p[3],p[4]]赋值为0即可。
对于求和，就是固定4个中的1个，求和过去。

------------------

叉姐的魔法训练（第五课）---- 如何成为一名合格的小学生

一 小学贪心

二 DP计数

一小学贪心