Chương trình đơn giản

Bạn chưa đăng nhập. Vui lòng đăng nhập để hỏi bài
Đạt Hoàng

Cho một dãy số a[n] và số nguyên s, hãy tìm dãy số dài nhất có tổng bằng s, nếu không có thì xuất “KHONG CO”.(0<n<1000; 0<a[i]<=100; 0<s<5000)

Tên file: Daysos.cpp

Dữ liệu vào: Daysos.inp

Dòng đầu chứa số nguyên n và s

Dòng tiếp theo chứa các số nguyên là phần tử của mảng a

Dữ liệu ra: Daysos.out

Dòng đầu là độ dài của dãy số dài nhất có tổng bằng s

Dòng tiếp theo là giá trị của các phần tử có trong dãy

Daysos.inp

Daysos.out

10 11

10 1 1 2 3 4 11 2 3 1

6

1 1 2 4 2 1

10 11

10 2 4 6 8 8 2 4 4 8

KHONG CO

Ai giúp mình bài này với ạ !

Just a bad coder
22 tháng 2 2020 lúc 17:05

#include <iostream>
#include <fstream>

int main()
{
std::ifstream f("daycon.inp");
int n,s,a[1001],d[100][1001];
f>>n>>s;
for(int i=1;i<=n;i++)
{
f>>a[i];
}
d[0][0]=0;
a[0]=0;
d[1][a[1]]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=s;j++)
{
d[i][j]=d[i-1][j];
if(j==a[i]&&d[i-1][j]<1)
d[i][j]=1;
else
if(a[i]<j&&d[i-1][j-a[i]]>0&&d[i-1][j-a[i]]+1>d[i][j])
d[i][j]=d[i-1][j-a[i]]+1;
}
}
for(int i=n;i>=1;i--)
{
if(d[i][s]!=d[i-1][s])
{
std::cout<<a[i]<<" ";
s-=a[i];
}
}

return 0;
}

Khách vãng lai đã xóa

Các câu hỏi tương tự
Thái Bảo
Xem chi tiết
Đinh Hoàng Nhất Quyên
Xem chi tiết
Nguyễn Thị Tươi
Xem chi tiết
Lê Thị Bảo Trâm
Xem chi tiết
Đức Huy
Xem chi tiết
Hứa Tiến Mạnh
Xem chi tiết
Đinh Hoàng Nhất Quyên
Xem chi tiết
Vân Ngô
Xem chi tiết
Nguyễn Thu Trang
Xem chi tiết