dp
HDU - 1257 最少拦截系统
最长递增子序列
#include<iostream>
using namespace std;
const int maxn=1e7;
int a[maxn],dp[maxn],n; int main()
{
while(cin>>n) {
for (int i = ; i <= n; i++)cin >> a[i];
for (int i = ; i <= n; i++)dp[i] = ;
for (int i = ; i <= n; i++)
for (int j = ; j < i; j++) {
if (a[i] > a[j])
dp[i] = max(dp[i], dp[j] + );
}
int ans = ;
for (int i = ; i <= n; i++)ans = max(ans, dp[i]);
cout << ans << endl;
}
return ;
}
HDU - 1029 Ignatius and the Princess IV
HDU - 1069 Monkey and Banana
POJ - 1458 Common Subsequence
最长公共子序列
dp[i][j] = 0 i==0 || j==0
= max(dp[i][j], dp[i-1][j-1]+1) a[i-1]==b[i-1]
= max(dp[i-1][j], dp[i][j-1]) a[i-1]!=b[i-1]
#include<string>
#include <iostream>
using namespace std;
const int maxn=1e4+;
int dp[maxn][maxn];
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
int len1=s1.size();
int len2=s2.size();
for(int i=;i<=len1;i++)
for(int j=;j<=len2;j++)
dp[i][j]=;
for(int i=;i<=len1;i++)
for(int j=;j<=len2;j++)
{
if((i==)||(j==))continue;
else if(s1[i-]==s2[j-])
dp[i][j]=max(dp[i][j],dp[i-][j-]+);
else
{
dp[i][j]=max(dp[i][j],dp[i][j-]);
dp[i][j]=max(dp[i][j],dp[i-][j]);
}
}
cout<<dp[len1][len2]<<endl;
}
return ;
}
POJ - 2533 Longest Ordered Subsequence
while(cin>>n)
{
for(int i=;i<=n;i++)cin>>a[i];
for(int i=;i<=n;i++)dp[i]=;
for(int i=;i<=n;i++)
{
for(int j=;j<i;j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+);
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
HDU - 1003 Max Sum
#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1e5+;
long long dp[maxn],a[maxn],ans=-0xfffffffffffff;
int n,t=,T=,l,r; int main()
{
cin>>n;
while(n--)
{
cin>>t;
T++;
for(int i=;i<=t;i++)cin>>a[i];
for(int i=-;i<=t;i++)dp[i]=a[i];
for(int i=;i<=t;i++)
dp[i]=max(dp[i-]+a[i],dp[i]);
for(int i=;i<=t;i++)
{
if(dp[i]>ans){
ans=max(ans,dp[i]);
r=i;
}
}
long long sum=;
for(int i=r;i>=;i--) {
sum += a[i];
if (sum == ans) {
l = i;
}
}
if(T!=)cout<<endl;
cout<<"Case "<<T<<":"<<endl;
cout<<ans<<" "<<l<<" "<<r<<endl;
}
return ;
}
HDU - 3421 Max Sum II
HDU - 1024 Max Sum Plus Plus
HDU - 1244 Max Sum Plus Plus Plus
HDU - 1087 Super Jumping! Jumping! Jumping!
HDU - 1114 Piggy-Bank
HDU - 1176 免费馅饼
HDU - 1160 FatMouse's Speed
POJ - 1661 Help Jimmy
HDU - 1260 Tickets
POJ - 3186 Treats for the Cows
HDU - 1078 FatMouse and Cheese
HDU - 2859 Phalanx
POJ - 3616 Milking Time
POJ - 3666 Making the Grade
HDU - 1074 Doing Homework
UVA - 11367 Full Tank?
POJ - 1015 Jury Compromise
题意：选m人：控方和辩方会根据对候选人的喜欢程度，给候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分D和控方总分P的差的绝对值|D-P|最小。如果有多种选择方案的 |D-P| 值相同，那么选辩控双方总分之和D+P最大的方案。
输出：要求输出这m个人的辩方总值D和控方总值P，并升序输出他们的编号
思路：
辩方总分和控方总分之差称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。
第i个候选人的辩方总分和控方总分之差记为V(i)，之和记为S(i)。
状态：dp[j][k]表示，取j个候选人，使其辩控差为k的所有方案中，辩控和最大的方案的辩控和。
如果没法选j个人，使其辩控差为k，那么dp(j, k)的值就为-1。
求：dp[m][k] (-20×m ≤ k ≤ 20×m)
转移方程：dp[j][k]= max ( dp[j-1][k-V[i]]+S[i], dp[j][k] )
方案dp[j][k]是由某个可行的方案 dp[j-1][x] 演化而来，可行方案 dp[j-1][x] 能演化成方案 dp[j][k] 的必要条件是：存在某个候选人i，i 在方案 dp[j-1][x] 中没有被选上，且x+V(i) = k。在所有满足该必要条件的dp[j-1][x]中，选出 dp[j-1][x]+ S(i) 的值最大的。
程序中没有求绝对值而是将辩控差都加上修正值fix=400，以免下标为负数导致出错，此时初始条件修正为dp[0][fix] = 0，其他均为-1。DP后，从第m行的dp(m, fix)开始往两边搜索最小|D-P| 即可，第一个不为dp[m][k]!=-1的位置k就是最小|D-P|的所在。
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int f[][];
//f[j][k]表示：取j个候选人，使其辩控差为k的方案中
//辩控和最大的那个方案（该方案称为“方案f(j,k)”)的控辩和
int Path[][];
//Path数组用来记录选了哪些人
//方案f(j,k)中最后选的那个候选人的编号，记在Path[j][k]中
int P[];//控方打分
int D[]; //辩方打分 int Answer[];//存放最终方案的人选 int main()
{
int i,j,k;
int t1,t2;
int n,m;
int MinP_D;//辩控双方总分一样时的辩控差
int Case;//测试数据编号
Case=;
while(scanf("%d %d",&n,&m))
{
if(n==&&m==)break;
Case++;
for(i=;i<=n;i++)
scanf("%d %d",&P[i],&D[i]);
memset(f,-,sizeof(f));
memset(Path,,sizeof(Path));
MinP_D=m*;//题目中的辩控差为0，对应于程序中的辩控差为m*20
f[][MinP_D]=;
for(j=;j<m;j++)//每次循环选出第j个人，共要选出m人
{
for(k=;k<=MinP_D*;k++)//可能的辩控差为[0，nMinP_D*2]
if(f[j][k]>=)//方案f[j][k]可行
{
for(i=;i<=n;i++)
if(f[j][k]+P[i]+D[i]>f[j+][k+P[i]-D[i]])
{
t1=j;t2=k;
while(t1>&&Path[t1][t2]!=i)//验证i是否在前面出现过
{
t2-=P[Path[t1][t2]]-D[Path[t1][t2]];
t1--;
}
if(t1==)
{
f[j+][k+P[i]-D[i]]=f[j][k]+P[i]+D[i];
Path[j+][k+P[i]-D[i]]=i;
}
}
}
}
i=MinP_D;
j=;
while(f[m][i+j]<&&f[m][i-j]<) // 从中间向两边开始找辩控差最小和最大
j++;
if(f[m][i+j]>f[m][i-j])
k=i+j;
else
k=i-j;
printf("Jury #%d\n",Case);
printf("Best jury has value %d for prosecution and value %d for defence:\n",(k-MinP_D+f[m][k])/,(f[m][k]-k+MinP_D)/);
for(i=;i<=m;i++)
{
Answer[i]=Path[m-i+][k];
k-=P[Answer[i]]-D[Answer[i]];
}
sort(Answer+,Answer++m);
for(i=;i<=m;i++)
printf(" %d",Answer[i]);
printf("\n\n");
}
return ;
}