HDU 4745 Two Rabbits
n块石头围成一个环，两只兔子各自选择起点，一只顺时针跳一只逆时针跳。一只兔子不能跳到或跳过它曾经跳到过的石头。每个时刻两只兔子脚下的石头重量需要相同。
思路：
思路：dp求最长回文子序列。由于是一个环，所以起始位置可以任何位置（两只兔子也可以在同一块石头上）。例如有11个数，1 2 3 4 3 2 1 8 9 9 8，从第七个数断开，左边是一个长度为7的回文串，右边是一个长度为4的回文串，假设起点从4开始，一只顺时针、另一只逆时针，可以发现走的最多步数是11，即断开的两个回文串之和。不用考虑起点问题，因为两边的中点都可以作为起点。
状态方程：dp(i,j)=max(dp(i+1,j),dp(i,j-1));表示从i到j的最长非连续回文子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1003;
int n;
int num[MAXN];
int dp[MAXN][MAXN];
void solve() {
for(int len = 2; len <= n; len++) {
for(int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
if(num[i] == num[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
}
}
}
int res = 0;
for(int i = 1; i <= n; i++) {
res = max(res, dp[1][i] + dp[i + 1][n]);
}
printf("%d\n", res);
}
int main() {
while(scanf("%d", &n) && n) {
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
dp[i][i] = 1;
}
solve();
}
}
|
HDU 4283 You Are the One
n个人站成一排。第i个人若是第k个上舞台的，会产生(k-1)*Di的不悦。在上舞台前，这n个人可以按序出入一个房间来调整顺序。这个房间有先进后出的性质。问调整后整体不悦值最低多少。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
#define inf 1<<27
#define N 105
using namespace std;
int dp[105][105];
int val[105],sum[105];
int main(){
int n,t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
sum[i]=sum[i-1]+val[i];
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
dp[i][j]=inf;
for(int l=1;l<=n-1;l++){
for(int i=1;i<=n-l;i++){
int j=i+l;
for(int k=i;k<=j;k++)
dp[i][j]=min(dp[i][j],val[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]);
}
}
printf("Case #%d: %d\n",++cas,dp[1][n]);
}
return 0;
}
|