目录

P5520 [yLOI2019] 青原樱

P5662 [CSP-J2019] 纪念品

P2066 机器分配

P5542 [USACO19FEB]Painting The Barn S

P2758 编辑距离

P1474 [USACO2.3]Money System / [USACO07OCT]Cow Cash G

P2725 [USACO3.1]邮票 Stamps

P1077 [NOIP2012 普及组] 摆花

P1095 [NOIP2007 普及组] 守望者的逃离

P3842 [TJOI2007]线段

P6208 [USACO06OCT] Cow Pie Treasures G

P2896 [USACO08FEB]Eating Together S

P2858 [USACO06FEB]Treats for the Cows G/S

P1440 求m区间内的最小值

P1388 算式

P1586 四方定理

---

P5520 [yLOI2019] 青原樱

        组合数学题目。

        A（n,m）= n * ( n - 1 ) * ( n - 2 ) * ... *( n - m + 1)

        C（n,m） = A（n,m）/ m ！

        本题考察插空法。推出公式ans=A（n-m+1 , m）；直接算

---

P5662 [CSP-J2019] 纪念品

        完全背包的变形，T天的股票每天的购进和第二天的卖出价格之差，作为物品的利润（val），每天股票的价格作为成本（体积），每日本金作为容积M。

int dp[10001];//dp[j]表示前i个物品在第k天用j元的最大盈利,j要开大一点 
int price[101][101];//price[i][j]表示i物品第j天的价格 for(int i=1;i<T;i++){memset(dp,0,sizeof(dp));//每一天交易过后清0 for(int j=1;j<=N;j++){for(int k=price[j][i];k<=M;k++)dp[k]=max(dp[k],dp[k-price[j][i]]-price[j][i]+price[j][i+1]);}M=M+dp[M];//M（容积）更新作为下一次交易的容积 }

---

P2066 机器分配

        背包，记录路径并输出。用最朴实的三维数组记录路径：

for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<=j;k++)if(f[i-1][k]+a[i][j-k]>f[i][j]){f[i][j]=f[i-1][k]+a[i][j-k];for(int l=1;l<i;l++)path[i][j][l]=path[i-1][k][l];path[i][j][i]=j-k;}

---

P5542 [USACO19FEB]Painting The Barn S

        二维差分。

	for(int i=1;i<=n;i++){int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);mp[x1+1][y1+1]++;mp[x2+1][y2+1]++;mp[x1+1][y2+1]--;mp[x2+1][y1+1]--;}for(int i=1;i<=1000;i++){for(int j=1;j<=1000;j++){mp[i][j]+=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];if(mp[i][j]==K)ans++;}}

---

P2758 编辑距离

        经典dp。

        有四种操作，分别为：

        1.删除：dp(i-1,j)+1：把字符串A的第i个字符删除，操作次数加一

        2.添加：dp(i,j-1)+1：在字符串A末添加字符串B的第j个字符，操作次数加一

        3.替换：dp(i-1,j-1)+1：将字符串A的第i个字符替换成字符串B的第j个字符，操作次数加一

        4.不变：dp（i-1,j-1）：如果字符串A的第i个字符等于字符串B的第j个字符，什么都不做

        处理边界情况：把dp[i][0]和dp[0][i]赋值为i，因为空字符串变成i个字符，用i次操作便可以。

    for(int i=1;i<=l1;i++)dp[i][0]=i;for(int i=1;i<=l2;i++)dp[0][i]=i;//初始化for(int i=1;i<=l1;i++)for(int j=1;j<=l2;j++)if(s1[i-1]==s2[j-1])//字符串是从零开始的所以要减1dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(dp[i-1][j-1]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));cout<<dp[l1][l2];

---

P1474 [USACO2.3]Money System / [USACO07OCT]Cow Cash G

        累加性背包dp。

	f[0]=1;for(int i=1;i<=v;i++){for(int j=a[i];j<=n;j++){f[j]+=f[j-a[i]];}}

---

P2725 [USACO3.1]邮票 Stamps

        完全背包变形。

    int i=0;//i为面值 while(f[i]<=k){i++;f[i]=1e9;for(int j=1;j<=n&&a[j]<=i;j++){f[i]=min(f[i],f[i-a[j]]+1);}}

---

P1077 [NOIP2012 普及组] 摆花

        dp[i][j]表示前i种花第i种连续排了j个的方案数。

    for(int i=0;i<=n;i++)dp[i][0]=1;for(int i=1;i<=n;i++){scanf("%d",&a[i]);for(int j=0;j<=a[i];j++){for(int k=0;k<=m-j;k++){if(j==0&&k==0) continue;dp[i][j+k]+=dp[i-1][k];dp[i][j+k]%=mod;}}}

---

P1095 [NOIP2007 普及组] 守望者的逃离

        本题是dp与贪心的结合。人飞的比跑得快，那么肯定优先飞，再考虑跑的情况。

    for(int i=1;i<=t;i++){if(m>=10){//能飞就飞f[i]=f[i-1]+60;m-=10;}else{//休息f[i]=f[i-1];m+=4;}}for(int i=1;i<=t;i++){if(f[i]<f[i-1]+17){//跑的更快就更新f[i]=f[i-1]+17;}if(f[i]>=s){printf("Yes\n%d",i);return 0;}}

---

P3842 [TJOI2007]线段

        状态设计要合理。f[i][0]表示人在第i行的左端点，1表示在右端点。

	f[1][0]=r[1]+r[1]-l[1]-1;f[1][1]=r[1]-1;for(int i=2;i<=n;i++){f[i][0]=min(f[i-1][0]+1+r[i]-l[i]+abs(r[i]-l[i-1]),f[i-1][1]+1+abs(r[i-1]-r[i])+r[i]-l[i]);f[i][1]=min(f[i-1][0]+1+abs(l[i]-l[i-1])+r[i]-l[i],f[i-1][1]+1+abs(r[i-1]-l[i])+r[i]-l[i]);}

---

P6208 [USACO06OCT] Cow Pie Treasures G

        坑点：对于不合法状态的考虑：左下角不会被走到，要么初值附上 ，要么for循环考虑周全。

	f[1][1]=maps[1][1];for(int j=2;j<=c;j++){for(int i=1;i<=r&&i<=j;i++){f[i][j]=max(f[i][j-1],max(f[i+1][j-1],f[i-1][j-1]))+maps[i][j];}}

---

P2896 [USACO08FEB]Eating Together S

        思路1：前后跑来确定最长不下降子序列（TLE）；

        思路2：可以用upper_bound优化（AC）；

	d[++len1]=a[1];for(int i=2;i<=n;i++){if(a[i]>=d[len1]){d[++len1]=a[i];}else{*upper_bound(d+1,d+1+len1,a[i])=a[i];}}t[++len2]=a[1];for(int i=2;i<=n;i++){if(a[i]<=t[len2]){t[++len2]=a[i];}else{*upper_bound(t+1,t+1+N,a[i],greater<int>())=a[i];}}printf("%d",n-max(len1,len2));

---

P2858 [USACO06FEB]Treats for the Cows G/S

        区间dp基本题目。

	for(int len=1;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;f[i][j]=max(f[i+1][j]+v[i]*(n-len+1),f[i][j-1]+v[j]*(n-len+1));}}

---

P1440 求m区间内的最小值

        单调队列可以解。

    q.push((node){1,p});printf("0\n");for(int i=2;i<=n;i++){scanf("%d",&p);node u=q.top();while(u.ord<i-m){q.pop();u=q.top();}q.push((node){i,p});printf("%d\n",u.num);}

---

P1388 算式

        区间dp和dfs结合的好题。我们可以凭借dfs遍历出乘号可能的位置，再利用区间dp求解最大值。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,a[20],flag[20],ans=-1;
int f[20][20];
int cal(int x,int y,int zz){return (zz==1)?x*y:x+y;
}
int dp(){memset(f,0,sizeof(f));for(int i=1;i<=n;i++)f[i][i]=a[i];for(int l=1;l<n;l++){for(int i=1;i+l<=n;i++){int j=i+l;for(int k=i;k<j;k++){f[i][j]=max(f[i][j],cal(f[i][k],f[k+1][j],flag[k]));}}}return f[1][n];
}
inline void dfs(int N,int cnt1,int cnt2){if(N==n){if(cnt1==k)ans=max(ans,dp());return;}else{if(cnt2<n-k-1)dfs(N+1,cnt1,cnt2+1);if(cnt1<k){flag[N]=1;dfs(N+1,cnt1+1,cnt2);flag[N]=0;}}
}
int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);dfs(1,0,0);printf("%d",ans);return 0;	
}

---

P1586 四方定理

        很有思维的一道递推题。

	f[0][0]=1;for(int i=1;i*i<=maxn;i++)for(int j=i*i;j<=maxn;j++){for(int k=1;k<=4;k++){f[j][k]+=f[j-i*i][k-1];}}