//由于时间关系（我太弱了），这些题目的Solution要等到NOIP 结束后再来填（可能最近刷题会填一些吧...）

//假装填了几题DP

Day 3

　　//　图论

BZOJ2330

POJ1236

POJ3648

POJ1511

POJ1797

POJ1062

BZOJ1821

POJ2728

BZOJ4078

Day4

　　//DP

（下面是讲义里的题目）

UVA 12212：数位翻转

SGU 134：中心

SGU 223：棋盘上的王

Poj2764：糖果

CF 279C：阶梯数列

HDU 2929：火柴

ZOJ 3349：特殊数列

CF506A：收集金币

POJ 3420：骨牌覆盖

POJ 3613：K边路

ZOJ 3031：捡垃圾

HDU 3156：圆覆盖

POJ 3418：二次函数

UVALive 5971: 排列计数

LA 5092：欧拉数

Tsinsen D7026：路径方案

Homework

以下是该网页的Solutioin：

Solution：

　　DP。

　　由于在固定的时间内考虑要与不要，而先采与后采没有区别，我们考虑DP。

　　采摘当前的价值高还是之前的高，取Max即可。

1 #include
       
         2 #include
        
          3 #define MAXN 105 4 #define MAXT 1005 5 using namespace std; 6 int t,mm; 7 int dp[MAXN][MAXT]; 8 struct Node{ 9     int t,v;10 };11 Node m[MAXN];12 inline int Max(int a,int b){
     return a>b?a:b;}13 int main(){14     memset(dp,0,sizeof(dp)); 15     scanf("%d%d",&t,&mm);16     for(int i=1;i<=mm;i++) scanf("%d%d",&m[i].t,&m[i].v);17     for(int i=1;i<=mm;i++) 18         for(int j=1;j<=t;j++) {19             if(j

Solution：

　　LIS。

　　用一个dp[i]来记录当前位置的最长上升长度，考虑要不要加入当前的值，对当前和之前取Max即可。

　　时间复杂度O（n^2）。

　　//　该网站第十题是一个O（nlogn）的LIS。

1 #include
       
         2 #define MAXN 1005 3 using namespace std; 4 int n,ans=0,dp[MAXN],a[MAXN]; 5 inline int Max(int a,int b){
     return a>b?a:b;} 6 int main(){ 7     scanf("%d",&n); 8     for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i]=1; 9     for(int i=1;i<=n;i++) 10         for(int j=1;j<=i;j++) {        11             if(a[i]>a[j]) dp[i]=Max(dp[j]+1,dp[i]);12             ans=Max(ans,dp[i]);13         }14     printf("%d",ans);15     return 0;16 }