POJ崩了……不知道什么时候才能好，爷想交题啊……

以下代码没交过，但dp能过样例应该就是对了吧.jpg

POJ-1260 Pearls

 题意：按顺序给出一些珍珠，后给出的一定比先给出的贵。每买一种珍珠除了购买数量的价钱，还必须付十颗珍珠的价钱。现给出要买珍珠的数量和价格，低级珍珠可以用高级珍珠替代，求最小代价。

解：可以省钱的地方在于如果低级珍珠数量较少，付十倍价钱肯定不划算。既然高级珍珠也要付十倍价钱，那么用高级珍珠替代低级就好了。如果第i种高级珍珠替代第j种低级珍珠可以省钱，那我肯定没必要用第i+1种替代。这样的替代可以将这些种类的珍珠分成好几组，有点像区间dp，但又不完全像。反正写起来倒比想着简单。

代码：

#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <string>
using namespace std;
#define ll long long
#define maxx 2005
#define eps 0.00000001
#define inf 0x3f
//#define int long long
int a[maxx],p[maxx];
int sum[maxx];
int dp[maxx];
signed main() {
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i],&p[i]);
        sum[0]=0;
        for(int i=1;i<=n;i++)
            sum[i]=a[i]+sum[i-1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1]+(a[i]+10)*p[i];
            for(int j=1;j<i;j++){
                dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1]+10)*p[i]);
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

View Code

POJ-1836 Alignment

题意：给一堆新兵排队。每个新兵的左边或右边必须有一边是递减的。求最少踢出去多少人能符合要求。

解：那就是排成一个 ^ 的样子。或者单增单减，但这可以被 ^ 包含。最开始的想法是设dp[i][0/1]表示到第i个，没拐弯/拐弯要剔除的最小人数，然后无脑转移，但直觉不对，或者做麻烦了。于是打开CSDN，发现求俩最长上升子序列然后n方找最小值就行了……n小就是好，求LIS都不用优化。

注意最高的可以有两个人。

代码：

#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <string>
using namespace std;
#define ll long long
#define maxx 2005
#define eps 0.00000001
#define inf 0x3f
//#define int long long
signed main() {
    int n;
    double a[maxx];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf",&a[i]);
    int dp1[maxx]={0},dp2[maxx]={0};
    dp1[1]=1;
    for(int i=2;i<=n;i++){
        dp1[i]=dp1[i-1];
        for(int j=1;j<i;j++)
            if(a[i]>a[j]&&dp1[i]<dp1[j]+1)
                dp1[i]=dp1[j]+1;
    }
    dp2[n]=1;
    for(int i=n-1;i>=1;i--){
        dp2[i]=dp2[i+1];
        for(int j=i+1;j<=n;j++)
            if(a[i]>a[j]&&dp2[i]<dp2[j]+1)
                dp2[i]=dp2[j]+1;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++)
            ans=max(ans,dp1[i]+dp2[j]);
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,dp1[i]+dp2[i]-1);
    printf("%d\n",n-ans);
    return 0;
}

View Code

POJ-3267 The Cow Lexicon

题意：奶牛又有词典了。先给出一串有杂音的叫声，再给出词典，求最少删除多少字母可以使得剩下的字符由词典里的词组成。

解：如果一个单词匹配上了字符串的子序列，那么拿现在要删的个数加上之前要删的个数即可。因为检查是否和第一个字母相同比较像正常人干的事，所以匹配要倒着来。

代码：

#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <string>
using namespace std;
#define ll long long
#define maxx 2005
#define inf 0x3f
//#define int long long
int dp[maxx]={0};
int w,l;
string s;
string dict[maxx];
signed main() {
    cin>>w>>l;
    cin>>s;
    for(int i=0;i<w;i++)
        cin>>dict[i];
    for(int i=l-1;i>=0;i--){
        dp[i]=dp[i+1]+1;
        for(int j=0;j<w;j++){
            //match
            int len=dict[j].length();
            if(s[i]==dict[j][0]) {
                int cnt = 0, pos = i;
                while (pos < l) {
                    if (dict[j][cnt] == s[pos++])
                        cnt++;
                    if (len == cnt) {
                        dp[i] = min(dp[i], dp[pos] + (pos - i) - len);
                        break;
                    }
                }
            }
        }
    }
    printf("%d\n",dp[0]);
    return 0;
}

View Code

POJ-1276 Cash Machine

题意：多重背包。没了。

解：二进制优化多重背包。最开始多重背包是把k件物品拆成k种物品然后做01背包，但这样三重循环太慢了。已知一个数可以拆成若干个2的n次幂之和的形式（谢谢高三数列大题），那么可以把k件物品按2的幂分堆，然后做01背包，复杂度从k直降为logk，很快乐。具体写法是如果能当成完全背包，也就是塞不下k件，按完全背包做。能塞下，二进制优化以下。

代码：

#include<stdio.h>
#include <algorithm>
#include <queue>
#include <stdlib.h>
using namespace std;
#define ll long long
#define maxx 200005
#define inf 0x3f
//#define int long long
int a[maxx],b[maxx];
int dp[maxx]={0};
int d,n;
void compack(int num,int w){
    if (num * w >= d) {
        for (int j = w; j <= d; j++){
            dp[j]=max(dp[j],dp[j-w]+w);
        }
    } else {
        int k=1;
        while(k<num){
            for(int j=d;j>=w*k;j--)
                dp[j]=max(dp[j],dp[j-k*w]+k*w);
            num-=k;
            k<<=1;
        }
        for(int j=d;j>=w*num;j--)
            dp[j]=max(dp[j],dp[j-w*num]+w*num);
    }
}
signed main() {
    while(~scanf("%d%d",&d,&n)){
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i],&b[i]);
        for(int i=1;i<=n;i++) {
            compack(a[i],b[i]);
        }
        printf("%d\n",dp[d]);
    }
    return 0;
}

View Code