HDU 1160

很生气的一道题…WA了好久都觉得自己是对的…debug了好久…发现是路径输出的时候发生了错误…本来是用

while(y!=0)
{
    printf("%d\n",m[y].id);
    y=pre[y];
}

这样来输出的，结果WA，然后用递归

void print(int pos)
{
    if(pos==0)return;
    print(pre[pos]);
    printf("%d\n",m[pos].id);
}

就AC了，不是说没有顺序规定的吗..,在这种条件下讲道理应该是一样的呀…究竟是怎么回事呢….哦…题目有坑…我以为是没有顺序的…其实这个任意一种的意思还是要按顺序的…有毒…题目都不讲清楚…

HDU 1024

题意：定一个数组，求其分成m个不相交子段和最大值的问题。

解题思路：设dp[i][j]表示前j个元素分成i组的最优解（j分好的组里面）
方程为dp[i][j]=max{d[i][j-1]+a[j],max(dp[i-1][k]+a[j])}(i-1<=k<=j-1)
第一种情况是j还在第i组里的最后一个
第二种情况是j自成一组，上一组最后一个为k，即第i-1组最大和
内存不够，就用滚动数组，观察到max( dp[i-1][k] ) 就是上一组 0....j-1 的最大值。我们可以在每次计算dp[i][j]的时候记录下前j个的最大值 用数组保存下来  下次计算的时候可以用.
方程就变成dp[i][j]=max(dp[j-1],pre[j-1])+a[j]。

核心代码：

int pre[1000010];//存上一层前j个的dp[k]的最大值
        for(i=1;i<=m;i++)
        {
            MAX=-INF;
            for(j=i;j<=n;j++)   //k的左界是i-1
            {
                dp[j]=max(dp[j-1],pre[j-1])+a[j];   //k的右界是j-1
                pre[j-1]=MAX;   //这一层的前j-1个的dp[k]的最大值
                MAX=max(MAX,dp[j]);   //把MAX更新一下
            }
        }
        printf("%d\n",MAX);

HDU 1114

HDU 2859

要注意可能有1*1这种数据…不能把ans初始化为-INF啊…

HDU 1074

状态压缩DP。

位运算在状压DP常见的应用如下：

1.判断一个数字x二进制下第i位是不是等于1。

方法：if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)

将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。

2.将一个数字x二进制下第i位更改成1。

方法：x = x | ( 1<<(i-1) )

3.把一个数字二进制下最靠右的第一个1去掉。

方法：x=x&(x-1)

代码及注释：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXN (1<<15)+10
using namespace std;
struct task
{
    char name[110];
    int limit,actu;
}t[20];
int dp[MAXN],Time[MAXN],path[MAXN];
//dp表示在此状态扣了多少分
//Time表示在此状态用了多少时间
//path表示到达状态i的前驱,为了最后输出完成作业的顺序
void output(int x)
{
    if(x==0)return;
    output(x-(1<<path[x]));
    printf("%s\n",t[path[x]].name);
}
int main()
{
    int T,i,j,n,tot,temp,score;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%s%d%d",t[i].name,&t[i].limit,&t[i].actu);
        memset(Time,0,sizeof(Time));
        int tot=1<<n;//所有状态
        for(i=1;i<tot;i++)
        {
            dp[i]=INF;
            for(j=n-1;j>=0;j--)//有两门作业完成后分数相同，在这种情况下，起初位于前面的作业位于前面
            {
                int temp=1<<j;
                if(!(i&temp))continue;//第j门没做
                int score=Time[i-temp]+t[j].actu-t[j].limit;//讲道理也不是很懂为什么是i-temp...
                if(score<0)score=0;
                if(dp[i-temp]+score<dp[i])//若最后做第j门作业，所扣的分数少于之前的分数
                {
                    dp[i]=dp[i-temp]+score;//作为此状态的最优解
                    Time[i]=Time[i-temp]+t[j].actu;//到达状态i花费的时间
                    path[i]=j;
                }
            }
        }
        printf("%d\n",dp[tot-1]);
        output(tot-1);
    }
    return 0;
}

POJ 3666

题意：给出长度为n的整数数列,每次可以将一个数加1或者减1,最少要多少次可以将其变成单调增或者单调减(不严格)。

解题思路：对于某个位置而言，一定改成和他前一个一样，或者和他后一个一样，所以最后形成的序列的数都在原序列里出现过，考虑b数组保存排完序后的原数组值，dp[i][j] = min(dp[i-1][k])+a[i]-b[j], 1<=k<=j。dp[i=当前考虑的前i个数][j=第i个数在总序列中排第j小]=当前的情况的最小改动量。什么意思呢，就是求当前dp[i][j]时候，考虑前i-1个数字，取第i-1个数字在第k（k=1…j）小中的最小改动量，再加上第i个数字成为第j小的改动量。

51nod 1007

题意：将一堆正整数分为2组，要求2组的和相差最小。**

解题思路：分成两组要相差最小，肯定是一组大于sum/2一组小于sum/2或者两组都是sum/2，就相当于其中一组与sum/2相差最小，然后转化为容量为sum/2的01背包问题即可。

51nod 1021

题意：现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

解题思路：

dp[i][j]：将i到j合并成一堆的最小代价
比如i=1,j=4,dp[1][4]=min(dp[1][3]+dp[4][4],dp[1][2]+dp[3][4],dp[1][1]+dp[2][4])+sum[1][4];

51nod 1084

题意：

一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

解题思路：
从左上角到右下角再回到左上角，这个过程可以看作从左上角同时走两路到右下角，我们记录两路当前的位置，这样就可以处理“同一个格子的数只能取一次”了。但是如果用dp[x1][y1][x2][y2]记录状态，这显然不可以。因为两路是同时走得，到达某一状态，它们走过的步数是相同，而且有了步数和行号就可以确定列号了，因此用dp[x1][x2][step]记录状态就可以了。

51nod 1202

题意：对于给出序列a，有些子序列可能是相同的，这里只算做1个，请输出a的不同子序列的数量。由于答案比较大，输出Mod 10^9 + 7的结果即可。

解题思路：假设dp[i]表示前i项形成的子序列（含空）的个数。下标从1开始，初值是dp[0] = 1，对应代表空子序列。我们考虑第i项，如果所有的数都不相等，应该有dp[i] = dp[i – 1] * 2，其实就是考虑把第i个数放到最后或者不放到最后的情况，原来恰好以第j个数结尾的那些被我们算了两次，因为以第j个数结尾可以换成以第i个数结尾是一样的。如何计算出这个数的个数呢？ 其实这个数等于dp[j – 1]，因为前面(j – 1)个数的子序列最后跟上第j个数就可以了。