DAG上的DP问题 嵌套矩形问题–NYOJ16 Problem Description
Input
Output
Sample Input
Sample Output
参考AC代码 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
struct node
{
int x,y;
}m[1050];
int d[1050];
int cmp(node a,node b)
{
if (a.x==b.x)
return a.y<b.y;
return a.x<=b.x;
}
int Max(node a,node b)
{
if (a.x<b.x&&a.y<b.y)
return 1;
return 0;
}
int main
{
/*freopen("input.txt" ,"r" ,stdin);*/
int t;
cin>>t;
while (t--)
{
int n;
cin>>n;
for (int i=0;i<n;i++)
{
cin>>m[i].x>>m[i].y;
if (m[i].x>m[i].y)
{
m[i].x=m[i].x^m[i].y;
m[i].y=m[i].x^m[i].y;
m[i].x=m[i].x^m[i].y;
}
}
memset(d,0,sizeof(d));
sort(m,m+n,cmp);
for (int i = 1; i < n; i++)
for (int j = 0; j <= i; j++)
if (Max(m[j],m[i])&&d[i] < d[j] + 1)
d[i] = d[j] + 1;
int maxn = d[0];
for (int i = 0; i < n; i++)
if (maxn < d[i])
maxn = d[i];
cout<<maxn+1<<endl;
}
return 0;
}
思路 按照先x后y的升序排列 后只需求LIS长度即可
嵌套盒子问题–UVA 103 题目要求 和嵌套矩阵类似
参考AC代码 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using namespace std;
struct node
{
int num[15]; //num里存储的是纬度
}a[35];
int k,n;
int d[35]; //代表以结点i为起点的最长路径
int map[35][35]; //邻接矩阵
int dp(int i) //记忆化搜索
{
int &ans=d[i]; //用引用可以避免数组d的纬度过大的情况 此题可不用引用
if (ans>0)
return ans;
ans=1;
for (int j=1;j<=n;j++)
if (map[i][j])
ans=max(ans,dp(j)+1); //状态转移方程 j必须和i为邻边
return ans;
}
void print_ans(int i) //这里的i是最后的id(起点) 以满足字典序
{
cout<<i<<" " ;
for (int j=1;j<=n;j++)
if (map[i][j]&&d[i]==d[j]+1) //只要d[i]=d[j]+1 立刻递归输出 第一个满足即为字典序
{
print_ans(j);
break ; //递归打印结束需要break
}
}
int main
{
freopen("input.txt" ,"r" ,stdin);
while (cin>>n>>k)
{
memset(map,0,sizeof(map));
memset(d,0,sizeof(d));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=k;j++)
cin>>a[i].num[j];
sort(a[i].num+1,a[i].num+1+k); //纬度里的数字升序排列
}
int flag1=0,flag2=0;
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
flag1=0;
flag2=0;
for (int h=1;h<=k;h++)
{
if (a[i].num[h]==a[j].num[h]) //和嵌套矩阵不同 不能等于
break ;
else if (a[i].num[h]<a[j].num[h])
flag1++;
else if (a[i].num[h]>a[j].num[h])
flag2++;
}
if (flag1==k) //若有一个纬度的点满足全部大于另一个点 那么建边
map[i][j]=1;
else if (flag2==k) ////若有一个纬度的点满足全部小于另一个点 那么建边
map[j][i]=1;
}
}
int Max=-1,id=-1;
for (int i=1;i<=n;i++)
{
dp(i);
if (d[i]>Max) //找出最大值和位置
{
Max=d[i];
id=i;
}
}
cout<<Max<<endl;
print_ans(id);
cout<<endl;
}
return 0;
}
硬币问题 题目：有n种硬币，面值分别为V1,V2,…Vn,每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值
参考代码(记忆化搜索) 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
33
34
35
36
37
38
39
using namespace std;
int n, S, V[MAXN], d[MAXN], vis[MAXN];
const int MAXN = 10000;
const int INF = 100000000;
int dpmax(int S)
{
if (vis[S]) return d[S];
vis[S] = 1;
int &ans = d[S];
ans = -1 << 30;
for (int i = 1; i <= n; ++i)
if (S >= V[i])
ans = max(ans, dpmax(S - V[i]) + 1);
return ans;
}
int dpmin(int S)
{
if (vis[S]) return d[S];
vis[S] = 1;
int &ans = d[S];
ans = -1 >> 30;
for (int i = 1; i <= n; ++i)
if (S >= V[i])
ans = min(ans, dpmin(S - V[i]) + 1);
return ans;
}
int main
{
memset(vis, 0, sizeof(vis));
cin >> n >> S;
for (int i = 1; i <= n; ++i)
cin >> V[i];
cout << dpmax(S) << endl;
cout << dpmin(S) << endl;
return 0;
}
参考代码(打印字典序最小路径) 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
const int MAXN = 10000;
const int INF = 1000000000;
int n, S, V[MAXN], minn[MAXN], maxn[MAXN];//minn[i]表示还需凑足价值为i的话，所需的最少的硬币数 maxn[i]表示还需凑足价值为i的话，所需的最多的硬币数
int min_coin[MAXN], max_coin[MAXN]; //min_coin[S]记录的是满足minn[S] = minn[S-V[i]]+1的最小的i。
void print_ans(int* d, int S)
{
while (S)
{
cout << d[S] << " " ;
S -= V[d[S]];
}
}
int main
{
cin >> n >> S;
for (int i = 1; i <= n; ++i)
cin >> V[i];
memset(minn, INF, sizeof(minn));
memset(maxn, -INF, sizeof(maxn));
for (int i = 1; i <= S; ++i)
{ //递推！求出所有minn[1...S]与maxn[1...S]
for (int j = 1; j <= n; ++j) {
if (i >= V[j])
{
if (minn[i] > minn[i - V[j]] + 1)
{
minn[i] = minn[i - V[j]] + 1;
min_coin[i] = j;
}
if (maxn[i] < maxn[i - V[j]] + 1)
{
maxn[i] = maxn[i - V[j]] + 1;
max_coin[i] = j;
}
}
}
}
cout << minn[S] << endl;
cout << maxn[S] << endl;
print_ans(min_coin, S);
cout << endl;
print_ans(max_coin, S);
cout << endl;
return 0;
}
