TÓM TẮT GIẢI THUẬT VÀ ĐÁP ÁN ĐỀ SỐ 4
Bài 1.
a. Ý tưởng thuật toán: Gán giá trị cần tìm maxx=0, thực hiện vòng lặp duyệt từng giá trị tại vị trí i, j, k. Sau đó gán tổng s=2a[i]-3a[j]+5*a[k]. Hàm maxx=max(s,maxx) sẽ cho ta kết quả cần tìm.
b. Chương trình nguồn:

include<bits/stdc++.h>

using namespace std;
long long i,j,k,n,s=0, a[1003],maxx=0;
int main()
{
freopen("BOMAX.INP","r",stdin);
freopen("BOMAX.OUT","w",stdout);
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
for(j=i+1;i<=n;i++)
for(k=j+1;i<=n;i++){
s=2a[i]-3a[j]+5*a[k];
maxx=max(s,maxx);
}
cout<<maxx;
}
Bài 2.
a. Ý tưởng thuật toán: Trước tiên ta tìm vị trí có số nhỏ nhất trong k kí tự đầu. Xóa các ký tự đầu của xâu s. Sau đó tìm các giá trị đầu tiên lớn nhất sau ký tự đầu và xoá đi.
b. Chương trình nguồn:

include<bits/stdc++.h>

using namespace std ;
string s;
long long k,minn,maxx=0;
int main ()
{
freopen("XOAKT.INP","r",stdin);
freopen("XOAKT.OUT","w",stdout);
cin>>s>>k;
for(int i=0;i<=k;i++)
{
if(s[minn]>s[i]){
minn=i;
}
}
s.erase(s.begin()+0,s.begin()+minn);
k=k-minn;
for(int i=1;i<=k;i++)
{
for(int j=0;j<=s.size()-1;j++)
{
if(s[maxx]<s[j]){
maxx=j;
}
}
s.erase(s.begin()+maxx);
maxx=0;
}
cout<<s;
}
Bài 3.
a. Ý tưởng thuật toán:

• Tính tổng các giá trị của mảng từ vị trí 1 cho đến vị trí v, (t[v]).
  • Tính tổng các giá trị của mảng từ vị trí 1 cho đến vị trí (u-1), t[u-1]
• Tổng các phần tử của mảng A từ phần tử thứ u đến phần tử thứ v là t[v]-t[u-1].
  b. Chương trình nguồn:

include <bits/stdc++.h>

using namespace std;
int n,q,i;
long long a[1000006],t[1000006];
int main()
{
freopen("MANG.INP", "r", stdin);
freopen("MANG.OUT", "w", stdout);
cin>>n>>q;
for(i=1;i<=n;i++) cin>>a[i];
t[0]=0;
for(i=1;i<=n;i++) t[i]=t[i-1]+a[i];
for(i=1;i<=q;i++)
{
int u,v;
cin>>u>>v;
cout<<t[v]-t[u-1]<<endl;
}
}

Bài 4.
a. Ý tưởng thuật toán: Phát biểu lại bài toán như sau: Cho m đoạn thẳng, đoạn thẳng i có điểm đầu, điểm cuối là si, ti và chi phí sử dụng đoạn thẳng i là ci. Tìm cách phủ một đoạn thẳng có điểm đầu, cuối là [0, n] với tổng chi phí là ít nhất. Khi đó ta thực hiện như sau:

• Sắp xếp tăng dần điểm cuối của mỗi đoạn thẳng, thêm một đoạn thẳng có điểm đầu, điểm cuối và chi phí sử dụng là 0, 0 ,0 vào vị trí đầu tiên của đoạn thẳng. Như vậy dãy đoạn thẳng cầ tìm luôn bắt đầu ở vị trí của đoạn thẳng vừa thêm vào.
• Sử dụng phương pháp Quy hoạch động: Gọi dp[i] là tổng chi phí sử dụng khi xét các nghệ sĩ từ đoạn thứ 0 đến đoạn thứ i. Khi đó min(dp[j]) trong đó tj>n là kết quả của bài toán.
  b. Chương trình nguồn:

include<bits/stdc++.h>

define N 400

define inf int(1e9)

using namespace std;
struct singer
{
int s,t,c;
};
singer a[N+2];
int dp[N+2];
int n,m,ans=inf;
bool cmp(singer X,singer Y)
{
return X.t<Y.t; } int main() { freopen("VANNGHE.INP","r",stdin); freopen("VANNGHE.OUT","w",stdout); cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i].s>>a[i].t>>a[i].c;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m+1;i++)
{
dp[i]=inf;
for(int j=0;j<i;j++)
if(a[i].s<=a[j].t)
{
dp[i]=min(dp[i],dp[j]+a[i].c);
if(n<=a[i].t) ans=min(ans,dp[i]);
}
}
cout<<ans;
return 0;
}