/*

标题不能太长，所以写这了

poj_2533_Longest Ordered Subsequence　poj_1260_Pearls　hdu_1025_Constructing Roads In JGShining‘s King　hdu_1074_Doing Homework

*/

poj_2533_Longest Ordered Subsequence

http://poj.org/problem?id=2533

LIS 不解释 ==

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int n;
	cin>>n;
	int a[1010];
	int dp[1010];
	for (int i=0;i<n;i++){
		cin>>a[i];
	}
	int ans=1;
	for (int i=0;i<n;i++){
		dp[i]=1;
		for (int j=0;j<i;j++){
			if(a[i]>a[j]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
}

http://poj.org/problem?id=1260

有n种珍珠，价额越高，质量越好，购买时每种应付款（数量+10）*单价；

原计划n种珍珠，第i种买ai颗，价格pi；（价p i>p i-1）

现在需要求换种方案，使得购买的数量不变，且质量更好，总价更小，求总价。

价格更少的关键在于那个“+10”，

此外，替换珍珠是连续的一个段，如果第i+2种珍珠可以用来替换第i种，那么第i+1应该更便意。

so dp[i] = min ( dp[i] , dp[j] +（sum[i] - sum[j] + 10) * p[i] );

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF=999999999;

struct Node {
	int a,p;
}node[106];

bool cmp (Node a,Node b){
	return  a.p<b.p;
}

int main(){
    int c;
    cin>>c;
    while (c--){
        int n,sum=0;
        int dp[106];
        int s[106];
        dp[0]=0;s[0]=0;
        cin>>n;
        for (int i=1;i<=n;i++){
            cin>>node[i].a>>node[i].p;
            sum+=(node[i].a+10)*node[i].p;
            s[i]=s[i-1]+node[i].a;
        }
        sort(node,node+n,cmp);
        for (int i=1;i<=n;i++){
        	dp[i]=INF;
            for (int j=0;j<=i-1;j++){
            	dp[i]=min(dp[i],dp[j]+(s[i]-s[j]+10)*node[i].p);
            }
            // cout<<dp[i]<<" ";
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}

hdu_1025_Constructing Roads In JGShining‘s King

http://acm.hdu.edu.cn/showproblem.php?pid=1025

平行线上有一些城市，一边是富饶的，一边是贫困的。没坐父老的城市拥有一种资源，对应着有一座贫困的城市缺少改资源。

现在The King 希望修通富饶城市和贫困城市之间的马路来帮助他们（资源的拥有和缺少必须对应），但为了防止交通事故，不允许两条道路相交叉。

问最多修多少道路。

以贫困城市为数组下标，富饶城市为数组元素的值，求 LIS 。

==  题目好坑，O(nlogn)的方法猜不会TLE，（copy自白书）而且，road和roads啊啊啊啊啊==

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n;

const int INF=999999999;

int dp[500050];

int main(){
    int c(0);
    char road[2][10]={"road","roads"};
    while (scanf("%d",&n)!=EOF){
        int a[500050];
        for (int i=0;i<n;i++){
            int x,y;
            scanf ("%d%d",&x,&y);
            a[x-1]=y;
        }
        fill (dp,dp+n,INF);
        for (int i=0;i<n;i++){
            *lower_bound(dp,dp+n,a[i])=a[i];
        }
        int ans=lower_bound(dp,dp+n,INF)-dp;;
        printf ("Case %d:\nMy king, at most %d %s can be built.\n",++c,ans,road[ans!=1?1:0]);
    }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1074

给出n份作业的截止时间第 D 天和需要花费时间 C 天，没迟交一天扣一分。

开这题好几天了，一直没思路，虽然知道是状压dp，知道今天中午吃饭的时候才来灵感，用一维的dp。T^T,一直在想二维的。

把n份作业的做与没做压缩成一个二进制的 int 。第i位表示第i份作业有没有做。

如果s表示做完的集合，那么他可以由 {s}-{j} V {j} 得到。

 dp[s] = min( dp[s-(1<<j)] + s); ( s : 做第j份作业要罚的分,s = max( t[s] + Cs - Ds , 0 ) )；

路径还原：fa 数组记录由状态 fa[ i ]得到状态 i ；还原是用位运算加递归；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF 999999999

struct Work {
	string s;
	int d,c;
}w[16];


struct Node{
	int p,t;
};

int  fa[1<<15+6];
Node dp[1<<15+6];

void findway (int a,int b){
	int c=a-b;
	int k=0;
	while(c!=1){
		c>>=1;
		k++;
	}
	cout<<w[k].s<<endl;
}

void find (int f,int k){
	if (f!=k){
		find (fa[f],f);
		findway(k,f);
	}
}

int main(){
	int c;
	cin>>c;
	while (c--){
		int n;
		scanf("%d",&n);
		for (int i=0;i<n;i++){
			cin>>w[i].s>>w[i].d>>w[i].c;
		}
		for (int i=0;i<(1<<n);i++){
			dp[i].p=INF;dp[i].t=0;
			fa[i]=i;
		}
		dp[0].p=0;
		for (int i=1;i<(1<<n);i++){
			for (int j=0;j<n;j++){
				if (i&(1<<j)){
					int s;
					s=max(dp[i-(1<<j)].t+w[j].c-w[j].d,0);
					if(dp[i].p>=dp[i-(1<<j)].p+s){
						dp[i].p=dp[i-(1<<j)].p+s;
						fa[i]=i-(1<<j);
					}
					dp[i].t=dp[i-(1<<j)].t+w[j].c;
				}
			}
		}
		printf ("%d\n",dp[(1<<n)-1]);
		int k=(1<<n)-1;
		find(fa[k],k);
	}
	return 0;
}

poj_2533_Longest Ordered Su...　poj_1260_Pearls　hdu_1025_Constructing Roa... poj_2533_Longest Ordered