A HDU_2048 数塔
dp入门题——数塔问题；求路径的最大和；
状态方程：
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
dp[n][j] = a[n][j];
其中dp[i][j]: 深度为i的第j个结点的最大和;
/*
Problem: HDU-2048
Tips: Easy DP
dp[i][j]: 深度为i的第j个结点的最大和；
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
dp[n][j] = a[n][j];
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
int a[maxn][maxn], dp[maxn][maxn];
int n;
void DP()
{
memset(dp, , sizeof(dp));
for(int j = ; j <= n; j++) dp[n][j] = a[n][j];
for(int i = n-; i >= ; i--)
{
for(int j = ; j <= i; j++)
{
dp[i][j]=max(dp[i+][j], dp[i+][j+])+a[i][j];
}
}
printf("%d\n", dp[][]);
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ; i <= n; i++)
for(int j = ; j <= i; j++)
scanf("%d", &a[i][j]);
DP();
} return ;
}
B HDU_1176 免费馅饼
数塔问题变形
状态方程：
dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])+a[i][j]; (注意要从后往前推)
dp[i][10] = max(dp[i+1][j-1], dp[i+1][j])+a[i][10];
dp[i][0] = max(dp[i+1][j], dp[i+1][j+1])+a[i][0];
其中dp[i][j]：第i时刻在位置j的接到的最多馅饼数；
/*
Problem: HDU-2048
Tips: Easy DP
dp[i][j]: 深度为i的第j个结点的最大和;
dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])+a[i][j];
dp[i][10] = max(dp[i+1][j-1], dp[i+1][j])+a[i][10];
dp[i][0] = max(dp[i+1][j], dp[i+1][j+1])+a[i][0];
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
int dp[maxn][], a[maxn][];
int main()
{
int n;
while(scanf("%d", &n) && n)
{
memset(a, , sizeof(a));
int maxt = ;
int t, p;
for(int i = ; i < n; i++)
{
scanf("%d%d", &p, &t);
a[t][p]++;
maxt = max(maxt, t);
}
memset(dp, , sizeof(dp));
for(int j = ; j <= ; j++) dp[maxt][j] = a[maxt][j];
for(int i = maxt-; i >= ; i--)
{
for(int j = ; j <= ; j++)
{
dp[i][j] = max(dp[i+][j], max(dp[i+][j+], dp[i+][j-]))+a[i][j];
}
dp[i][] = max(dp[i+][], dp[i+][])+a[i][];
dp[i][] = max(dp[i+][], dp[i+][])+a[i][];
} printf("%d\n", dp[][]);
}
return ;
}
C HDU_1087 Super Jumping! Jumping! Jumping!
状态方程：
dp[j] = v[i]<v[j] ? dp[i]+v[j] : dp[j];
dp[0] = 0;
其中dp[j]: 到第j步时，棋子的最大和
感觉自己推的方程毫无技术含量
/*
Problem: HDU-2048
Tips: Easy DP
dp[j]: 到第j步时，棋子的最大和
dp[j] = v[i]<v[j] ? dp[i]+v[j] : dp[j];
dp[0] = 0;
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
int dp[maxn], v[maxn];
int main()
{
int n;
while(~scanf("%d", &n) && n)
{
memset(dp, , sizeof(dp));
int _max = ;
for(int i = ; i <= n; i++) {scanf("%d", &v[i]); dp[i] = v[i]; _max = max(_max, v[i]);}
dp[n+] = v[n+] = _max+; dp[] = v[] = ;
for(int i = ; i <= n; i++)
{
for(int j = i+; j <= n+; j++)
{
if(v[j] > v[i])
{
dp[j] = max(dp[j], dp[i]+v[j]);
}
}
}
printf("%d\n", dp[n+]-_max-);
}
return ;
}
E HDU_1058 Humble Numbers
求丑数。两种方法，之前一直用优先队列，dp的算法时间更短，这算法谁想出来的...
每个丑数都可以分解为2^a*3^b*5^c*7的乘积，每次找到最小的数分别乘以2，3，5，7然后放入队列中去。两种方法的基本原理都是这样。
dp：
/*
Problem: HDU 1058
Times: 62MS
Tips: Easy DP
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = ;
const int pri[] = {, , , };
LL dp[maxn];
LL Min(LL a, LL b, LL c, LL d)
{
return min(a, min(b, min(c, d)));
} void init()
{
int p1, p2, p3, p4;
p1 = p2 = p3 = p4 = ;
dp[] = ;
int a, b, c, d;
for(int i = ; i <= ; i++)
{
a = dp[p1]*;
b = dp[p2]*;
c = dp[p3]*;
d = dp[p4]*;
dp[i] = Min(a, b, c, d);
if(dp[i] == a) p1++;
if(dp[i] == b) p2++;
if(dp[i] == c) p3++;
if(dp[i] == d) p4++;
}
} int main()
{
init();
int n;
while(~scanf("%d", &n) && n)
{
if(n% == && n% != )
{
printf("The %dst humble number is %I64d.\n", n, dp[n]);
}
else if(n% == && n% != )
{
printf("The %dnd humble number is %I64d.\n", n, dp[n]);
}
else if(n% == && n% != )
{
printf("The %drd humble number is %I64d.\n", n, dp[n]);
}
else
printf("The %dth humble number is %I64d.\n", n, dp[n]);
} return ;
}
优先队列：
/*
Problem: HDU 1058
Times: 109MS
Tips: Easy DP
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<algorithm>
#define LL long long
using namespace std;
//typedef long long LL;
const int pri[] = {, , , };
LL ans[]; void init()
{
priority_queue<LL, vector<LL>, greater<LL> > pq;
set<LL> s;
pq.push(); s.insert();
for(int i = ; ; i++)
{
LL x = pq.top(); pq.pop();
ans[i] = x;
if(i == ) return ;
for(int j = ; j < ; j++)
{
LL t = pri[j]*x;
if(!s.count(t))
{
s.insert(t);
pq.push(t);
}
}
}
} int main()
{
init();
int n;
while(~scanf("%d", &n) && n)
{
if(n% == && n% != )
{
printf("The %dst humble number is %I64d.\n", n, ans[n]);
}
else if(n% == && n% != )
{
printf("The %dnd humble number is %I64d.\n", n, ans[n]);
}
else if(n% == && n% != )
{
printf("The %drd humble number is %I64d.\n", n, ans[n]);
}
else
printf("The %dth humble number is %I64d.\n", n, ans[n]); }
return ;
}
G HDU_1159 Common Subsequence
LIC入门题+滚动数组
状态方程：
dp[i][j] = (s[i]==s2[j]) ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
其中dp[i][j] :s1串到i处，s2串到j处时最长上升子串的长度；
由状态方程可以看出，只需要知道i-1时的状态就可以推出i时的状态，因此可以只用一个2*maxn的数组存储状态值，那么看方程也可以根据j-1的状态推出j时的状态啊为什么不用2*2的？虽然方程表面上看来是这样，但是别忘了j是随着i的递增而循环的，每次i改变，状态量都会更新；
/*
Problem: HDU 1159
Tips: LCS
*/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<algorithm>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
char s1[maxn], s2[maxn];
int dp[][maxn];
void LCS()
{
int l1 = strlen(s1+), l2 = strlen(s2+);
memset(dp, , sizeof(dp));
for(int i = ; i <= l1; i++)
{
for(int j = ; j <= l2; j++)
{
if(s1[i] == s2[j])
dp[i%][j] = dp[(i-)%][(j-)]+;
else
dp[i%][j] = max(dp[(i-)%][j], dp[i%][(j-)]);
}
}
printf("%d\n", dp[l1%][l2]);
} int main()
{
while(~scanf("%s%s", s1+, s2+))
{
LCS();
}
return ;
}
H HDU_1003 Max Sum
最大连续子串和入门题；blog有原题题解，不再赘述。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<algorithm>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
int n;
int a[maxn];
int dp[maxn]; void DP()
{
memset(dp, , sizeof(dp));
int _max = -INF;
int s, e; s = e = ;
for(int i = ; i <= n; i++)
{
dp[i] = dp[i-]> ? dp[i-]+a[i] : a[i];
if(dp[i] > _max)
{
_max = dp[i]; e = i;
}
}
printf("%d ", _max);
s = e;
for(int i = e; i >= ; i--)
{
if(dp[i]<) break;
s = i;
}
printf("%d %d\n", s, e);
} int main()
{
int T; scanf("%d", &T);
for(int kase = ; kase < T; kase++)
{
if(kase) printf("\n");
printf("Case %d:\n", kase+);
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
DP();
}
return ;
}
I HDU_4540 威威猫系列故事——打地鼠
状态方程：
dp[i][j] = min(dp[i-1][pos_last]+abs(pos_last-pos_now));
dp[0][j] = dp[1][j] = 0;
其中dp[i][j]: 第i时刻打位于j位置的地鼠消耗能量的最小值。
/**/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<algorithm>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = ;
const int maxp = ;
int n, k;
int a[maxn][maxn];
int dp[maxn][maxp];
void DP()
{
memset(dp, INF, sizeof(dp));
for(int p = ; p < maxp; p++) dp[][p] = ;
for(int t = ; t <= n; t++)
for(int j = ; j < k; j++)
{
int pos_now = a[t][j];
int _min = INF;
for(int p = ; p < k; p++)
{
int pos_last = a[t-][p];
_min = min(_min, dp[t-][pos_last]+abs(pos_last-pos_now));
}
dp[t][pos_now] = _min;
}
int _min = dp[n][];
for(int p = ; p < k; p++)
_min = min(_min, dp[n][a[n][p]]);
printf("%d\n", _min);
} int main()
{
while(~scanf("%d%d", &n, &k))
{
for(int t = ; t <= n; t++)
for(int p = ; p < k; p++)
scanf("%d", &a[t][p]);
DP();
}
return ;
}